wyrażenia regularne w rzeczywistości posiadają zwykle dodatkowe możliwości, i generują więcej języków niż tylko języki regularne.
Twierdzenie Myhilla-Nerode’a Twierdzenie Myhilla-Nerode’a podaje dostateczny i konieczny warunek na to, by język był regularny.
Przykład Weźmy język słów o parzystej ilości jedynek i nieparzystej ilości zer. Język ten jest regularny, i prefiksy można pogrupować w 4 klasy: prefiksy o parzystej ilości jedynek i zer – prawidłowe sufiksy mają parzyście wiele jedynek i nieparzyście wiele zer, prefiksy o parzystej ilości jedynek i nieparzystej zer – prawidłowe sufiksy mają parzyście wiele jedynek i zer, prefiksy o nieparzystej ilości jedynek i parzystej zer – prawidłowe sufiksy mają nieparzyście wiele jedynek i zer, prefiksy o nieparzystej ilości jedynek i zer – prawidłowe sufiksy mają parzyście wiele zer i nieparzyście wiele jedynek.
Przykład (2) Weźmy język czyli wszystkich słów składających się z znaków po których występuje znaków dla dowolnego
Weźmy ciąg prefiksów postaci dla kolejnych należy do zbioru poprawnych sufiksów dla prefiksu wtedy i tylko wtedy, gdy należy do tego języka, a więc gdy Czyli zbiory poprawnych sufiksów dla każdych dwóch prefiksów z naszego nieskończonego ciągu są różne, co przez twierdzenie o indeksie dowodzi, że język ten nie jest regularny.