Myhill-Nerode teorem

Izvor: Wikipedija

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[uredi | uredi kôd]

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, ako započnemo s 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 s 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[uredi | uredi kôd]

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, ako 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 s 3 je regularan. Postoje 3 klase ekvivalencije: brojevi koji daju ostatke 0, 1 i 2 pri dijeljenju s 3. Minimalni automat koji prihvaća ovaj jezik bi imao tri stanja koja korespondiraju klasama ekvivalencije.

Vanjske poveznice[uredi | uredi kôd]