Myhill-Nerodes sætning

I teorien om formelle sprog definerer Myhill-Nerode-sætningen en nødvendig og tilstrækkelig betingelse for et sprogs regelmæssighed .

Sætningen er opkaldt efter John Myhillog Anil Nerodesom beviste det ved University of Chicago i 1958 . [en]

Udtalelse af sætningen

Lad der være et sprog i alfabetet og en relation på ord fra mængden af alle ord i det givne alfabet er givet sådan, at hvis og kun hvis for alle , der hører til mængden af alle ord i det givne alfabet, både ord og samtidig hører hjemme eller samtidig ikke tilhører sproget . Det er let at bevise, at der er en ækvivalensrelation på mængden af ord i alfabetet . $L$ $V$ $\equiv _{L}$ $x\equiv _{L}y$ $z$ $xz$ $yz$ $L$ $\equiv _{L}$ $V$

Ved Myhill-Nerode-sætningen er antallet af tilstande i en minimal deterministisk finit automat (DFA), der accepterer et sprog , lig med antallet af ækvivalensklasser med hensyn til , det vil sige styrken af sprogets faktorsæt med respekt til . Dette tal kaldes også indekset for en binær relation og betegnes som . $L$ $\equiv _{L}$ $L$ $\equiv _{L}$ $ind\equiv _{L}$

Bevis

Konsekvenser

Det følger af Myhill-Nerode-sætningen, at et sprog er regulært, hvis og kun hvis antallet af ækvivalensklasser er endeligt. Man kan umiddelbart konkludere, at hvis relationen deler sproget i et uendeligt antal ækvivalensklasser, så er sproget ikke regulært. Denne konklusion bruges meget ofte til at bevise sprogets uregelmæssighed. $L$ $\equiv _{L}$ $\equiv _{L}$ $L$ $L$

Se også

Vækst Lemma

Noter

↑ A. Nerode, "Linear automaton transformations", Proceedings of the AMS , 9 (1958) s. 541-544.

Litteratur

Tom Henzinger, Foredrag 7: Myhill-Nerode-sætning (2003)
Myhill-Nerode-sætningen (noter fra klasser på kurset "Teori og implementering af programmeringssprog", FUPM MIPT).

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme