Twierdzenie Myhilla-Nerode'a

Z Wikipedii

W teorii języków formalnych twierdzenie Myhilla-Nerode'a podaje konieczne i dostateczne warunki na to, by dany język był regularny.

Niech $L$ będzie językiem nad alfabetem $Σ$ . 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 $Σ *$ 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.

[edytuj] Przykłady

język $L = a n b n$ nie jest regularny - rozpatrzmy bowiem ciąg słów $a, aab, aaab,\dots, a^{k}b, \dots$ ; dowolne dwa słowa $a k b$ i $a m b$ , $k \neq m$ są rozróznialne sufiksem $u = b k - 1$ - relacja $R L$ ma zatem nieskończenie wiele klas abstrakcji, czyli L nie jest regularny

Kategoria: Języki formalne

We provide Linux to the World

Twierdzenie Myhilla-Nerode'a

Z Wikipedii

[edytuj] Przykłady

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach