Myhill-Neroden lause

Formaalisten kielten teoriassa Myhill-Neroden lause määrittelee kielen säännöllisyydelle välttämättömän ja riittävän ehdon .

Lause on nimetty John Myhillin mukaanja Anil Nerodejoka osoitti sen Chicagon yliopistossa vuonna 1958 . [yksi]

Lauseen lause

Olkoon aakkostossa kieli ja suhde sanoihin kaikista annetun aakkoston sanojen joukosta on annettu siten, että jos ja vain jos kaikille , jotka kuuluvat annettujen aakkosten kaikkien sanojen joukkoon, molemmat sanat ja samanaikaisesti kuuluvat tai samanaikaisesti eivät kuulu kieleen . On helppo todistaa, että se on ekvivalenssisuhde aakkosten sanajoukossa . $L$ $V$ $\equiv _{L}$ $x\equiv _{L}y$ $z$ $xz$ $yz$ $L$ $\equiv _{L}$ $V$

Myhill-Nerode-lauseen mukaan kielen hyväksyvän minimideterministisen äärellisen automaattin (DFA) tilojen määrä on yhtä suuri kuin ekvivalenssiluokkien lukumäärä suhteessa , eli kielen tekijäjoukon potenssi suhteessa . . _ Tätä lukua kutsutaan myös binäärirelaation indeksiksi ja se merkitään . $L$ $\equiv _{L}$ $L$ $\equiv _{L}$ $ind\equiv _{L}$

Todiste

Seuraukset

Myhill-Neroden lauseesta seuraa, että kieli on säännöllinen silloin ja vain, jos ekvivalenssiluokkien lukumäärä on äärellinen. Voidaan heti päätellä, että jos relaatio jakaa kielen äärettömään määrään ekvivalenssiluokkia, kieli ei ole säännöllinen. Tätä johtopäätöstä käytetään hyvin usein todistamaan kielten epäsäännöllisyyttä. $L$ $\equiv _{L}$ $\equiv _{L}$ $L$ $L$

Katso myös

Kasvu Lemma

Muistiinpanot

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

Kirjallisuus

Tom Henzinger, Luento 7: Myhill-Neroden lause (2003)
Myhill-Neroden lause (kurssin "Ohjelmointikielten teoria ja toteutus", FUPM MIPT) tuntien muistiinpanot.

Muodolliset kielet ja viralliset kieliopit
Yleiset käsitteet	Chomsky-hierarkia Aakkoset Sana
Tyyppi 0	Rajoittamaton kielioppi Turingin kone lueteltu kieli Ratkaiseva kieli
Tyyppi 1	Tilanneherkkä kielioppi Tilannekohtainen kieli Lineaarisesti rajattu automaatti
Tyyppi 2	Kontekstiton kielioppi Epäselvä kielioppi Kontekstiton kieli Työntöautomaatti ( deterministinen ) Kasvu Lemma Ogdenin Lemma Cookin lause
Tyyppi 3	Tavallinen kielioppi tavallinen kieli Tavallinen ilme Tilakone ( deterministinen , ei - deterministinen ) DFA-minimointi NFA:n määrittäminen Myhill-Neroden lause
jäsentäminen	LL analysaattori LR jäsentäjä Rekursiivinen laskeutumismenetelmä Kok-Younger-Kasami-algoritmi