Myhillova-Nerodova věta

V teorii formálních jazyků Myhill-Nerode teorém definuje nezbytnou a postačující podmínku pro regularitu jazyka.

Věta je pojmenována po Johnu Myhillovia Anil Nerodekterý to dokázal na University of Chicago v roce 1958 . [jeden]

Prohlášení věty

Nechť je v abecedě jazyk a u slov z množiny všech slov v dané abecedě je dán takový vztah , že právě tehdy, když pro všechna patřící do množiny všech slov v dané abecedě patří obě slova a současně nebo současně nepatří do jazyka . Je snadné dokázat, že jde o vztah ekvivalence na množině slov v abecedě . $L$ $PROTI$ $\equiv _{L}$ $x\equiv _{L}y$ $z$ $xz$ $yz$ $L$ $\equiv _{L}$ $PROTI$

Podle Myhill-Nerodeovy věty je počet stavů v minimálním deterministickém konečném automatu (DFA), který přijímá jazyk, roven počtu tříd ekvivalence s ohledem na , to je síla množiny faktorů jazyka s ohledem na do . Toto číslo se také nazývá index binární relace a označuje se jako . $L$ $\equiv _{L}$ $L$ $\equiv _{L}$ $ind\equiv _{L}$

Důkaz

Důsledky

Z Myhill-Nerodovy věty vyplývá, že jazyk je regulární právě tehdy, když je počet tříd ekvivalence konečný. Lze okamžitě dojít k závěru, že pokud vztah rozděluje jazyk do nekonečného počtu tříd ekvivalence, pak jazyk není regulární. Tento závěr se velmi často používá k dokazování nepravidelnosti jazyků. $L$ $\equiv _{L}$ $\equiv _{L}$ $L$ $L$

Viz také

Růstové lemma

Poznámky

↑ A. Nerode, "Transformace lineárních automatů", Proceedings of the AMS , 9 (1958) s. 541-544.

Literatura

Tom Henzinger, Přednáška 7: Myhill-Nerode Theorem (2003)
Myhill-Nerode teorém (poznámky z předmětu "Teorie a implementace programovacích jazyků", FUPM MIPT).

Formální jazyky a formální gramatiky
Obecné pojmy	Chomského hierarchie Abeceda Slovo
Typ 0	Neomezená gramatika Turingův stroj výčtový jazyk Řešitelný jazyk
Typ 1	Kontextově citlivá gramatika Kontextový jazyk Lineárně ohraničený automat
Typ 2	Bezkontextová gramatika Nejednoznačná gramatika Bezkontextový jazyk Zásobníkový automat ( deterministický ) Růstové lemma Ogdenovo lemma Cookova věta
Typ 3	Pravidelná gramatika regulární jazyk Regulární výraz Stavový stroj ( deterministický , nedeterministický ) Minimalizace DFA Stanovení NFA Myhillova-Nerodova věta
rozebrat	LL analyzátor LR analyzátor Metoda rekurzivního sestupu Kok-Younger-Kasami algoritmus