Myhill-Nerodes sats

I teorin om formella språk definierar Myhill-Nerode-satsen ett nödvändigt och tillräckligt villkor för ett språks regelbundenhet .

Satsen är uppkallad efter John Myhilloch Anil Nerodesom bevisade det vid University of Chicago 1958 . [ett]

Uttalande av satsen

Låt det finnas ett språk i alfabetet och en relation på ord från mängden av alla ord i det givna alfabetet ges så att om och bara om för alla som hör till mängden av alla ord i det givna alfabetet, både ord och samtidigt tillhör eller samtidigt inte tillhör språket . Det är lätt att bevisa att det är en ekvivalensrelation på mängden ord i alfabetet . $L$ $V$ $\equiv _{L}$ $x\equiv _{L}y$ $z$ $xz$ $yz$ $L$ $\equiv _{L}$ $V$

Enligt Myhill-Nerode-satsen är antalet tillstånd i en minimal deterministisk finit automat (DFA) som accepterar ett språk lika med antalet ekvivalensklasser med avseende på , det vill säga kraften i språkets faktoruppsättning med avseende på till . Detta tal kallas också index för en binär relation och betecknas som . $L$ $\equiv _{L}$ $L$ $\equiv _{L}$ $ind\equiv _{L}$

Bevis

Konsekvenser

Det följer av Myhill-Nerodes sats att ett språk är regelbundet om och endast om antalet ekvivalensklasser är ändligt. Man kan omedelbart dra slutsatsen att om relationen delar upp språket i ett oändligt antal ekvivalensklasser, så är språket inte regelbundet. Denna slutsats används mycket ofta för att bevisa språkens oegentligheter. $L$ $\equiv _{L}$ $\equiv _{L}$ $L$ $L$

Se även

Tillväxt Lemma

Anteckningar

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

Litteratur

Tom Henzinger, föreläsning 7: Myhill-Nerode-satsen (2003)
Myhill-Nerode-satsen (anteckningar från klasser på kursen "Teori och implementering av programmeringsspråk", FUPM MIPT).

Formella språk och formella grammatiker
Allmänna begrepp	Chomsky hierarki Alfabet Ord
Typ 0	Obegränsad grammatik Turing maskin uppräknat språk Lösbart språk
Typ 1	Sammanhangskänslig grammatik Kontextkänsligt språk Linjärt begränsad automat
Typ 2	Kontextfri grammatik Tvetydig grammatik Kontextfritt språk Pushdown-automat ( deterministisk ) Tillväxt Lemma Ogdens Lemma Cooks teorem
Typ 3	Vanlig grammatik vanligt språk Vanligt uttryck Tillståndsmaskin ( deterministisk , icke- deterministisk ) DFA-minimering Bestämning av NFA Myhill-Nerodes sats
analysera	LL analysator LR-parser Rekursiv nedstigningsmetod Kok-Yngre-Kasami-algoritm