Twierdzenie Myhilla-Nerode’a

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Twierdzenie Myhilla-Nerode'a)
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]

Niech będzie językiem nad alfabetem . Zdefiniujmy relację sufiksowej nieodróżnialności następująco: wtedy i tylko wtedy, gdy dla każdego słowa u wtedy i tylko wtedy, gdy .

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

Nieformalnie, jeśli język L jest regularny, to klasy abstrakcji relacji odpowiadają stanom automatu skończonego rozpoznającego L. Innymi słowy „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]

  • język nie jest regularny – rozpatrzmy bowiem dwa słowa: oraz dla . Jeśli teraz podstawimy oraz to sufiks rozróżnia te dwa słowa, gdyż oraz . Zatem relacja ma zatem nieskończenie wiele klas abstrakcji, czyli L nie jest regularny.