U teoriji formalnih jezika, Myhill-Nerode teorem pruža nužne i dovoljne uvjete da bi jezik bio regularan. Gotovo se isključivo koristi prilikom dokazivanja neregularnosti nekog danog jezika.
Teorem je imenovan po Johnu Myhillu i Anil Nerode, koji su ga dokazali na čikaškom sveučilištu 1958.
Iskaz teorema
Za dani jezik L definirajmo relaciju RL nad nizovima znakova pravilom x RL y ako ne postoji istaknuta ekstenzija z sa sa svojstvom da točno jedan od nizova znakova xz i yz jest element skupa L. Lako se pokazuje da je RL relacija ekvivalencije nad nizovima znakova, te stoga dijeli skup svih konačnih nizova znakova u jednu ili više klasa ekvivalencije.
Myhill-Nerode teorem kaže da je broj stanja u najmanjem automatu koji prihvaća L jednak broju klasa ekvivalencije u RL. Intuicija koja leži iza ovog iskaza jest ta da, ukoliko započnemo sa takvim minimalnim automatom, tada bilo koji nizovi znakova x i y koji ga vode u isto stanje će biti u istoj klasi ekvivalencije; te ako započnemo sa particijom u klase ekvivalencije, lako možemo konstruirati automat koji koristi svoje stanje u svrhu praćenja klase ekvivalencije koja sadrži dio niza znakova koji je dotad pročitan.
Uporaba i posljedice
Posljedica Myhill-Nerode teorema jest da jezik L je regularan (tj. prihvaća ga konačni automat) ako i samo ako je broj klasa ekvivalencije RL konačan.
Direktan korolar koji slijedi jest da, ukoliko jezik definira beskonačan skup klasa ekvivalencije, tada on nije regularan. Baš ovaj korolar se često koristi prilikom dokaza neregularnosti jezika.
Na primjer, jezik koji se sastoji od binarnih brojeva djeljivih sa 3 je regularan. Postoje 3 klase ekvivalencije - brojevi koji daju ostatke 0, 1 i 2 pri dijeljenju sa 3. Minimalni automat koji prihvaća ovaj jezik bi imao tri stanja koja korespondiraju klasama ekvivalencije.