Teorema Myhill-Nerode

În teoria limbajelor formale, teorema Myhill-Nerode definește o condiție necesară și suficientă pentru regularitatea unei limbi.

Teorema este numită după John Myhillși Anil Nerodecare a dovedit-o la Universitatea din Chicago în 1958 . [unu]

Enunțul teoremei

Să existe o limbă în alfabet și o relație asupra cuvintelor din setul tuturor cuvintelor din alfabetul dat este dată astfel încât dacă și numai dacă pentru toate aparținând setului tuturor cuvintelor din alfabetul dat, ambele cuvinte și simultan aparțin sau simultan nu aparţin limbii . Este ușor de demonstrat că este o relație de echivalență pe mulțimea de cuvinte din alfabet . $L$ $V$ $\equiv _{L}$ $x\equiv _{L}y$ $z$ $xz$ $yz$ $L$ $\equiv _{L}$ $V$

Prin teorema Myhill-Nerode, numărul de stări dintr-un automat determinist finit minim (DFA) care acceptă un limbaj este egal cu numărul de clase de echivalență față de , adică puterea setului de factori a limbajului față de la . Acest număr este numit și indicele unei relații binare și este notat ca . $L$ $\equiv _{L}$ $L$ $\equiv _{L}$ $ind\equiv _{L}$

Dovada

Consecințele

Din teorema Myhill-Nerode rezultă că o limbă este regulată dacă și numai dacă numărul claselor de echivalență este finit. Se poate concluziona imediat că dacă relația împarte limba într-un număr infinit de clase de echivalență, atunci limbajul nu este regulat. Această concluzie este foarte des folosită pentru a dovedi neregularitatea limbilor. $L$ $\equiv _{L}$ $\equiv _{L}$ $L$ $L$

Vezi și

Lema de creștere

Note

↑ A. Nerode, „Linear automaton transformations”, Proceedings of the AMS , 9 (1958) pp. 541-544.

Literatură

Tom Henzinger, Cursul 7: Teorema Myhill-Nerode (2003)
Teorema Myhill-Nerode (note ale orelor la cursul „Teoria și implementarea limbajelor de programare”, FUPM MIPT).

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tip 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami