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.

Laat L een formele taal zijn. Twee woorden x en y zijn L-equivalent als voor alle woorden z geldt, dat ${\displaystyle xz\in L}$ dan en slechts dan als ${\displaystyle 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.

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.

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

Bewijs. Beschouw de oneindige rij woorden ${\displaystyle a^{i}}$, voor ${\displaystyle i=1,2,3\ldots }$. Als ${\displaystyle i\neq j}$ geldt dan, dat ${\displaystyle a^{i}}$ en ${\displaystyle a^{j}}$ niet L-equivalent aan elkaar zijn, omdat voor ${\displaystyle z=b^{i}}$ geldt, dat ${\displaystyle a^{i}z\in L}$ maar ${\displaystyle 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.

• Pompstelling

• 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.