Myhill-Nerode tétel

A formális nyelvek elméletében a Myhill-Nerode tétel egy nyelv szabályszerűségének szükséges és elégséges feltételét határozza meg .

A tétel nevét John Myhillről kaptaés Anil Nerodeaki a Chicagói Egyetemen 1958 -ban bebizonyította . [egy]

tétel állítása

Legyen egy nyelv az ábécében , és az adott ábécé összes szavainak halmazából olyan reláció adható meg a szavakon, hogy akkor és csak akkor, ha az adott ábécé összes szóhalmazához tartozó összes szóhoz egyidejűleg mind a két szó tartozik . vagy egyidejűleg nem tartoznak a nyelvhez . Könnyű bebizonyítani, hogy ez egy ekvivalencia reláció az ábécé szavak halmazán . $L$ $V$ $\equiv _{L}$ $x\equiv _{L}y$ $z$ $xz$ $yz$ $L$ $\equiv _{L}$ $V$

A Myhill-Nerode tétel szerint egy nyelvet elfogadó minimális determinisztikus véges automatában (DFA) az állapotok száma megegyezik az ekvivalencia osztályok számával , azaz a nyelv tényezőhalmazának hatványával . hogy . Ezt a számot bináris reláció indexének is nevezik , és jelölése . $L$ $\equiv _{L}$ $L$ $\equiv _{L}$ $ind\equiv _{L}$

Bizonyítás

Következmények

A Myhill-Nerode tételből következik, hogy egy nyelv akkor és csak akkor szabályos, ha az ekvivalenciaosztályok száma véges. Azonnal levonható a következtetés, hogy ha a reláció a nyelvet végtelen számú ekvivalenciaosztályra bontja, akkor a nyelv nem reguláris. Ezt a következtetést nagyon gyakran használják a nyelvek szabálytalanságának bizonyítására. $L$ $\equiv _{L}$ $\equiv _{L}$ $L$ $L$

Lásd még

Növekedési Lemma

Jegyzetek

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

Irodalom

Tom Henzinger, 7. előadás: Myhill-Nerode tétel (2003)
A Myhill-Nerode tétel (a „Programozási nyelvek elmélete és megvalósítása”, FUPM MIPT kurzus osztályainak jegyzetei).

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus