Twierdzenie Myhilla-Nerode'a

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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.