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

Twierdzenie Myhilla-Nerode’a orzeka, że język L jest regularny wtedy i tylko wtedy, gdy relacja ${\displaystyle R_{L}}$ dzieli ${\displaystyle \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 ${\displaystyle R_{L}.}$

Nieformalnie, jeśli język L jest regularny, to klasy abstrakcji relacji ${\displaystyle R_{L}}$ odpowiadają stanom automatu skończonego rozpoznającego L. Innymi słowy ${\displaystyle 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 ${\displaystyle L={a^{n}b^{n}}}$ nie jest regularny – rozpatrzmy bowiem dwa słowa: ${\displaystyle a^{k}b^{k}}$ oraz ${\displaystyle a^{k+c}b^{k+c}}$ dla ${\displaystyle c\geqslant 1.}$ Jeśli teraz podstawimy ${\displaystyle w=a^{k}b^{k}}$ oraz ${\displaystyle v=a^{k+c}b^{k}}$ to sufiks (postfiks) ${\displaystyle u=b^{c}}$ rozróżnia te dwa słowa, gdyż ${\displaystyle wu\notin L}$ oraz ${\displaystyle vu\in L.}$ Zatem relacja ${\displaystyle R_{L}}$ ma zatem nieskończenie wiele klas abstrakcji, czyli L nie jest regularny.