Twierdzenie Myhilla-Nerode'a

Twierdzenie Myhilla-Nerode'a – twierdzenie w teorii języków formalnych podające konieczne i dostateczne warunki na to, by dany język był regularny. Zostało udowodnione w 1958 roku przez Johna Myhilla i Anila Nerode'a.

Twierdzenie

Niech $L$ będzie językiem nad alfabetem $\Sigma$. Zdefiniujmy relację sufiksowej nieodróżnialności $R_{L} \subseteq \Sigma^{*} \times \Sigma^{*}$ następująco: $(w,v) \in R_{L}$ wtedy i tylko wtedy, gdy dla każdego słowa u $wu \in L$ wtedy i tylko wtedy, gdy $vu \in L$.

Twierdzenie Myhilla-Nerode'a orzeka, że język L jest regularny wtedy i tylko wtedy, gdy relacja $R_{L}$ dzieli $\Sigma^{*}$ na skończenie wiele klas abstrakcji. Dodatkowo, jeśli L jest regularny, to liczba stanów minimalnego deterministycznego automatu skończonego rozpoznającego L jest równa liczbie klas abstrakcji relacji $R_{L}$.

Nieformalnie, jeśli język L jest regularny, to klasy abstrakcji relacji $R_{L}$ odpowiadają stanom automatu skończonego rozpoznającego L. Innymi słowy $R_{L}$ "skleja" ze sobą słowa, których "przyszłości" z punktu widzenia zachowania automatu są identyczne. Intuicyjnie, jeśli klas abstrakcji jest nieskończenie wiele, to automat rozpoznający L musiałby mieć nieskończenie wiele stanów, co jest niemożliwe.

Przykłady

• język $L={a^{n}b^{n}}$ nie jest regularny - rozpatrzmy bowiem dwa słowa: $a^{k}b^{k}$ oraz $a^{k+c}b^{k+c}$ dla $c \geq 1$. Jeśli teraz podstawimy $w = a^{k}b^{k}$ oraz $v = a^{k+c}b^{k}$ to sufiks $u = b^{c}$ rozróżnia te dwa słowa, gdyż $wu \not\in L$ oraz $vu \in L$. Zatem relacja $R_{L}$ ma zatem nieskończenie wiele klas abstrakcji, czyli L nie jest regularny.