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 $\mathrm{\Sigma }.$ Zdefiniujmy relację sufiksowej nieodróżnialności $R_L\subseteq {\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}$ następująco: $(w,v)\in R_L$ wtedy i tylko wtedy, gdy dla każdego słowa $u\in {\mathrm{\Sigma }}^{*},$ $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 ${\mathrm{\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⩾1.$ Jeśli teraz podstawimy $w=a^k{b}^k$ oraz $v=a^{k+c}{b}^k$ to sufiks (postfiks) $u=b^c$ rozróżnia te dwa słowa, gdyż $wu\notin L$ oraz $vu\in L.$ Zatem relacja $R_L$ ma zatem nieskończenie wiele klas abstrakcji, czyli L nie jest regularny.