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]
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 .
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 .
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.
Formális nyelvek és formális nyelvtanok | |
---|---|
Általános fogalmak | |
Típus 0 | |
1. típus |
|
2. típus | |
3. típus |
|
elemzése |