Stelling van Myhill-Nerode

De stelling van Myhill-Nerode geeft een noodzakelijke en voldoende voorwaarde die aangeeft wanneer een formele taal regulier is. De stelling luidt, dat een formele taal regulier is, dan en slechts dan als haar Myhill-Nerode-equivalentie eindig veel equivalentieklassen heeft. De stelling werd genoemd naar de wiskundigen John Myhill en Anil Nerode, die haar in 1958 voor het eerst bewezen.

Definitie

Laat L een formele taal zijn. Twee woorden x en y zijn L-equivalent als voor alle woorden z geldt, dat $xz\in L$ dan en slechts dan als $yz\in L$. De equivalentie die zo ontstaat wordt Myhill-Nerode-equivalentie van L genoemd. De stelling van Myhill-Nerode luidt, dat de taal L regulier is dan en slechts dan als de Myhill-Nerode-equivalentie van L eindig veel equivalentieklassen bezit.

De Myhill-Nerode equivalentieklassen komen overeen met de toestanden in de minimale deterministische eindige automaat die de taal accepteert.

Gebruik

Aangezien de stelling van Myhill-Nerode een noodzakelijke en voldoende voorwaarde voor regulariteit aangeeft, kan ze zowel gebruikt worden om te bewijzen dat een taal regulier is als om te bewijzen dat een taal niet regulier is.

Voorbeeld

Stelling. De taal $L=\{a^{n}b^{n}\mid n\in \mathbb {N} \}$ is niet regulier.

Bewijs. Beschouw de oneindige rij woorden $a^{i}$, voor $i=1,2,3\ldots$. Als $i\neq j$ geldt dan, dat $a^{i}$ en $a^{j}$ niet L-equivalent aan elkaar zijn, omdat voor $z=b^{i}$ geldt, dat $a^{i}z\in L$ maar $a^{j}z\notin L$. Dat betekent dat de Myhill-Nerode-equivalentie van L oneindig veel equivalentieklassen bezit, en daarom volgt uit de stelling van Myhill-Nerode dat L niet regulier is.

Zie ook

• Pompstelling

Literatuur

• John E. Hopcroft, Rajeev Motwani en Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley, 2006.
• Uwe Schöning. Theoretische Informatik - Kurz gefasst (5. Auflage). Spektrum, 2008.