Myhill-Neroden teoreema

Olen vuosikaudet opettanut tietojenkäsittelyteorian erilaisia kursseja, ja yksi asia joka useimmilla alan peruskursseilla käsitellään on niin kutsutut säännölliset kielet. Formaalien kielten teoriassa ei ole samalla tavalla kyse kielistä kuin vaikkapa lingvistiikassa, vaikka yhtymäkohtia tieyiltä osin tietenkin on. Pääosin näitä asioita käsitellään siten että "kieli" ymmärretään joukoksi merkkijonoja; vaihtoehtoisesti voidaan ajatella että "kieli" on merkkijonojen predikaatti; jotkut merkkijonot toteuttavat kyseisen ominaisuuden ja jotkut eivät.

Säännölliset kielet ovat kaikkein yksinkertaisin jollain tavalla relevantti formalismi. Kielen säännöllisyys voidaan määritellä monella tavalla ja päätyä samaan lopputulokseen. Yksi tapa määritellä säännölliset kielet on siten, että kun on annettu aakkosto E, niin määritellään säännölliset lausekkeet aakkoston yli. Oletamme että meillä on tyhjän joukon symboli ø ja tyhjän merkkijonon symboli e, jotka eivät kuulu aakkostoon. Säännöllinen lauseke muodostetaan seuraavasti:

1. ø ja e ovat säännöllisiä lausekkeita
2. jokainen aakkoston E symboli a on yksinään säännöllinen lauseke
3. Jos R ja S ovat säännöllisiä lausekkeita, niin RS on säännöllinen lauseke
4. Samoin R+S on säännöllinen lauseke,
5. R* on säännöllinen lauseke kun R on säännöllinen lauseke. 

Kukin säännöllinen lauseke R määrittelee joukon L(R) merkkijonoja. L(ø) ei sisällä mitään merkkijonoa, L(e) = {e}, eli sisältää vain tyhjän merkkijonon, ja L(a) = {a} jokaiselle yksittäiselle aakkossymbolille. L(R+S) määrittelee joukon joka on L(R):n ja L(S):n yhdiste. L(RS) määrittelee joukon L(R)*L(S), joka muodostuu kaikista L(R):n merkkijonoista joiden perään on laitettu mielivaltainen L(S):n merkkijono. L(R*) määrittelee joukon jossa on kaikki sellaiset merkkijonot jotka saadaan muodostettua laittamalla R:n mielivaltaisia merkkijonoja perätysten mielivaltainen määrä. (Myös nolla kertaa, eli L(R*) sisältää aina tyhjän merkkijonon)

Yhtäpitävä määritelmä saadaan kun sovitaan että kieli on säännöllinen jos on olemassa jokin äärellinen automaatti joka hyväksyy kielen. Äärellinen automaatti on yksinkertainen kone, jossa on äärellinen määrä tiloja. Ennen merkkijonon lukemista automaatti on alkutilassaan. Aina kun automaatti lukee syötteenään aakkoston symbolin, se siirtyy johonkin tilaan; siirtymä riippuu tilasta jossa ollaan ja symbolista joka luetaan. Osa tiloista on ns hyväksymistiloja, ja jos merkkijono päättyy kun automaatti on hyväksymistilassa, automaatti hyväksyy kyseisen merkkijonon.

Formaalien kielten teoriassa on niin sanottu erottavan jatkeen käsite. Jos meillä on kaksi merkkijonoa x ja y, niin kolmas merkkijono z on erottava jatke kielen L suhteen, jos tasan toinen merkkijonoista xz ja yz kuuluu kieleen L. Jos kahdelle merkkijonolle ei ole erottavaa jatketta, niin riippumatta merkkijonon z valinnasta xz ja yz molemmat joko kuuluvat tai eivät kuulu kieleen L.

Esimerkiksi, jos aakkosto koostuu merkeistä a ja b, ja kieli L koostuu kaikista niistä merkkijonoista joissa on yhtä monta a- ja b-merkkiä, niin jos x:ssä ja y:ssä on yhtä monta a:ta ja b:tä, niin x:llä ja y:llä ei ole erottavaa jatketta. Itse asiassa tämä pätee jos a- ja b-merkkien määrän erotus on x:ssä ja y:ssä sama.

Sanomme, että merkkijonot x ja y ovat ekvivalentit kielen L suhteen, jos niille ei ole erottavaa jatketta. Tämä ekvivalenssirelaatio jakaa kaikki merkkijonot ekvivalenssiluokkiin. Myhill-Neroden teoreema sanoo, että kieli L on säännöllinen jos ja vain jos kielen L suhteen on olemassa vain äärellinen määrä ekvivalenssiluokkia.

Koska kieli on säännöllinen jos ja vain jos sille löytyy äärellinen automaatti, niin voimme todistaa tämän väitteen toiseen suuntaan melko helposti: Jos kaksi merkkijonoa vie automaatin samaan tilaan, niin merkkijonojen on oltava automaatin kielen suhteen ekvivalentteja; ekvivalenssiluokkia ei voi olla enempää kuin kielen hyväksyvässä automaatissa on tiloja.

Kääntäen, jos ekvivalenssiluokkia on äärellinen määrä, voimme muodostaa automaatin joka hyväksyy kielen. Automaatissa on yksi tila jokaista ekvivalenssiluokkaa kohden. Alkutila vastaa ekvivalenssiluokkaa, johon tyhjä merkkijono kuuluu. Tilasiirtymä tapahtuu ekvivalenssiluokkien välillä siten, että jos x on mielivaltainen tilaan q liittyvän ekvivalenssiluokan alkio, niin tilasiirtymä a vie tilasta q tilaan q' siten että q':a vastaava ekvivalenssiluokka sisältää merkkijonon xa.  Tämä toimii, sillä jos x ja y ovat ekvivalentteja, niillä ei ole erottavaa jatketta. Koska niillä ei ole erottavaa jatketta, ei myöskään merkkijonoilla xa ja ya voi olla erottavaa jatketta.

Hyväksymistiloiksi valitaan tilat joita vastaavan ekvivalenssiluokan alkiot kuuluvat kieleen. Kaikki ekvivalenssiluokan alkiot tietenkin kuuluvat tai mikään ei kuulu, sillä tyhjä merkkijono ei ole kyseisten merkkijonojen erottava jatke.

Tällä tavalla rakennettu automaatti on itseasiassa pienin mahdollinen äärellinen automaatti joka kyseisen kielen hyväksyy. Tilojen määrää voidaan pitää alkeellisena kielen kompleksisuuden mittarina, joskin tämä ei vastaa perinteisemmän kompleksisuusteorian kompleksisuusmittoja. Jokainen säännöllinen kieli ratkeaa ilman lisämuistia ajassa, joka kuluu merkkijonon lukemiseen, joten jokainen säännöllinen kieli on laskennallisesti äärimmäisen yksinkertainen. Nimitämme tätä suuretta kielen indeksiksi.

Jokaiselle (myös ei-säännölliselle) kielelle A voidaan esittää pari säännöllisiä kieliä (L,U) siten, että L ja U ovat säännöllisiä, L on A:n osajoukko, joka puolestaan on U:n osajoukko. No, tämä on triviaalisti totta, koska tyhjä joukko ja kaikkien merkkijonojen joukko ovat säännöllisiä. Mielenkiintoisempi kysymys -- johon vastaaminen kertoo paljon kielen A monimutkaisuudesta -- on se, miten tarkkoja approksimaatioita voidaan löytää, kun kielten L ja U indeksien summa (esimerkiksi) on n. Approksimaation tarkkuutta voidaan esimerkiksi mitata siten, että kun otetaan mielivaltainen merkkijono x, mikä on todennäköisyys että x kuuluu L:ään ja A:han tai ei kuulu A:han eikä U:hun, eli kääntäen, mikä on todennäköisyys että x:stä päätellään "väärin" se, kuuluuko se A:han. Mutta tämä teoria menee jo sitten vähän pidemmälle.