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  dan en slechts dan als . 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  is niet regulier.

Bewijs. Beschouw de oneindige rij woorden , voor . Als  geldt dan, dat  en  niet L-equivalent aan elkaar zijn, omdat voor  geldt, dat  maar . 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.

Formele taal