Chomsky klassifikatsioon

Formaalsed grammatikad leiutati peaaegu samaaegselt kahes kohas, erinevate uurijate poolt erineval eesmärkidel: esimese programmeerimiskeele Fortran süntaksi kirjeldamiseks ja loomulike keelte (inglise, eesti jne) lausestruktuuri kirjeldamiseks. Lingvist ja matemaatik Noam Chomsky, kes esimesena esitas formaalsete grammatikate süstemaatilise definitsiooni, esitas samas ka grammatikate klassifikatsiooni, milles grammatikad jagati nelja järjest suuremasse (iga järgnev klass sisaldab eelmist) klassi. Kuigi Chomsky klassifikatsioon põhineb täiesti formaalsetel tunnustel, osutus hiljem, et klasside omadused peegeldavad nende abil kirjeldatavate keelte struktuuri, keelte tunnistamise keerukust jne.

Chomsky liigitus põhineb produktsioonide kujul.

  • 0-tyypi (e. rekursiivselt loenduvate) grammatikate produktsioonidele kitsendusi ei ole.
  • 1-tüüpi (e. kontekstitundlike) grammatikate kõik produktsioonid peavad olema kujul

    w1Xw2 w1vw2

    kus X on mitteterminal, w1, w2, v - suvalised sõnad mis võivad sisaldada nii terminale kui ka mitteterminale ja v ei ole tühi (s.t. mitteterminali X asendamine sõnaga v on lubatud vaid kontekstis w1.. w2); erandina on lubatud produktsioon Xo  ( - tühi sõna), kui algussümbol Xo ei esine ühegi produktsiooni paremal pool. Saab näidata, et iga selle klassi grammatika poolt kirjeldatud keelt võib esitada ka nn. pikkust suurendava grammatikaga, st. grammatikaga, mille kõik produktsioonid w w' rahuldavad tingimust |w| |w'|
  • 2-tüüpi e. kontekstivabade grammatikate kõik produktsioonid peavad olema kujul X v, kus X on mitteterminal;
  • 3-tüüpi e. regulaarsete grammatikate kõik produktsioonid peavad olema kujul

    X aY
    või
    X a

    kus X,Y on mitteterminalid ja a - terminal. Saab näidata, et regulaarsete grammatikate poolt genereeritud keeled saab kirjeldada ka grammatikatega, mille produktsioonid on vasakpoolsed, s.t. kujul
    X Ya või X a

    Selles klassifikatsioonis iga järgmine klass kuulub eelmisesse (s.t. näiteks regulaarsed grammatikad rahuldavad kõiki kontekstivabade grammatikate klassi nõudeid), selleärast laieneb Chomsky klassifikatsioon loomulikul viisil ka keeltele: keelt nimetatakse klassi i (i=3,2,1,0 ) keeleks ehk vastavalt regulaarseks, kontekstivabaks, kontekstitundlikuks, rekursiivselt loenduvaks, kui teda saab genereerida klassi i grammatikaga ja ei saa genereerida klassi i+1 (s.t. rangema, kitsama klassi) grammatikaga.

    Vaatamata liigituse formaalsele alusele (produktsioonide kuju) on Chomsky klassifikatsioonil sügav sisu.

    Grammatikad on (formaalne) struktuur keelte genereerimiseks, kuid nende abil ei saa (ei ole lihtne) otsustada, millisesse klassi mingi keel kuulub - kas näiteks programeerimiskeele identifikaatorid (määratud tingimusega: "Identifikaator peab algama tähega, edasi võivad tulla tähed või numbrid") moodustavad regulaarse keele või mitte - kuid see on oluline skanneri tegemisel. Grammatika abil on sellisele küsimusele raske vastata. Kui me oleme koostanud keele jaoks (näiteks) kontekstivaba grammatika, siis on keel (vähemalt) kontekstivaba, kuid kuidas näidata, et seda grammatikat ei saa teisendada nii, et ta vorm vastaks regulaarse grammatika definitsioonile - siis oleks keel regulaarne?

    Keelte liigitamiseks (ja paljude teiste probleemide lahendamiseks) kasutatakse automaate. Automaat hakkab keelde kuuluvaid märgijadasid (sõnu) lugema ja kui automaat sõna lõppedes on lõppolekus, siis ütleme, et automaat tunnistas keele, s.t. keel kuulub selle automaadiga tunnistatavate keelte klassi. Igale Chomsky klassile vastab selle klassi keeli tunnistavate automaatide klass.

    kolme olekuga automaatRegulaarseid keeli tunnistavad lõplikud automaadid. Kuna lõpliku automaadi ainus mälu on tema olekud, siis öeldakse ka, et regulaarseid keeli saab tunnistada lõpliku mäluga. Lõpliku automaadiga (mäluga) saab tunnistada näiteks keele

    {w | w kuulub{0,1}*, |w|1= 0(mod 3)}

    s.t. keele, mis koosneb 0,1-jadadest (bitijadadest), milles 1-de arv jagub kolmega. Sellise keele tunnistamiseks on tarvis vaid kolme olekuga automaati - sisend 1 viib alati järgmisesse olekusse, sisend 0 olekut ei muuda; kui automaat sõna lõppedes on taas algolekus, jagus ühtede arv sõnas kolmega ja sõna kuulus keelde.

    Kontekstivabade keelte tunnistamiseks on tarvis juba lõpmatut mälu, kuid automaat võib kasutada seda väga piiratud kujul - magasinina. Magasinmäluga automaat suudab näiteks tunnistada keele

    {w1 = w2 | w1, w2kuulub{0,1}*, |w1|1 = |w2|1 }

    s.t. bitijadade võrdused w1 = w2, kus 1-de arv võrdusmärgi mõlemal pool on võrdne - sellise keele tunnistamiseks salvestab magasinmäluga automaat kõik enne võrdusmärki loetud 1-d magasinis ja pärast võrdusmärki kustutab iga sisendilt loetud 1-ga ka magasinist ühe 1 ; kui sõna lõppedes magasin on tühi, oli ühtede arv võrdne.

    Kontekstitundlikke ja 0-klassi keeli tunnistavad Turingi masinad, kuid kontekstitundlikke keeli tunnistav Turingi masina mälulint ei või olla pikem kui sisendlint (seda nn lineaarselt piiratud mäluga Turing-i masina definitsiooni võib esitada mitmel kujul sõltuvalt tungimustest, mis seatakse sellise Turingi masina sisendtähestikule).

    Ka programmeerimiskeeltes esineb elemente, mida ei saa kirjeldada regulaarse ega kontekstivabade grammatikatega, s.t. mis on oma loomult kontekstitundlikud või rekursiivselt loenduvad; selline on näiteks nn range tüübikontrolliga programmeerimiskeeltes (Java!) esinev nõue, et kõik identifikaatorid peavad olema enne kasutamist deklareeritud. Lihtsustame veidi ja vaatleme keelt, mis koosneb vaid identifikaatoritest (tavalise süntaksiga: algab tähega ja edasi võivad tulla tähed või numbrid) ja identifikaatori deklaratsioonidest kujul DEF ident, kus DEF on fikseeritud lekseem ja ident - mingi identifikaator. Keel koosneb kõikvõimalikest jadadest, mille iga element on kas paar DEF ident (identifikaatori deklaratsioon) või lihtsalt mingi identifikaator ident (identifikaatori ident kasutamine), kuid iga identifikaatori ident jaoks peab kusagil varem leiduma selle deklaratsioon DEF ident. Lihtne on näha, et sellist keelt ei ole võimalik magasini abil tunnistada. Tunnistav automaat peaks magasinis salvestama kõik deklaratsioonid DEF ident, kuid kui ta tahab mingi identifikaatori ident jaoks kontrollida, kas selle deklaratsioon DEF ident on magasinis olemas, peab ta hakkama magasinis salvestatud deklaratsioone ühekaupa välja viskama (magasinmäluga automaadi operatsioon "pop"), kuni leiab õige - kuid neid väljavisatud deklaratsioone võib olla kuitahes palju (ülalesitatud identifikaatori süntaksi kirjeldus lubab moodustada lõpmatu arvu identifikaatoreid), seega ei suuda ta neid kusagil salvestada (peale magasini on automaadil vaid lõplik arv olekuid), s.t. keel ei ole kontekstivaba (saab näidata, et see keel on kontekstitundlik).

    Paljud keelte käsitlemisel olulised omadused, näiteks keeli tunnistava programmi töökiirus ja mäluvajadus jne on seda paremad, mida lihtsama klassi keeli vaadeldakse. Sellepärast püütakse translaatorite alametappidel (leksikaanalüüs, süntaksi analüüs jne) kasutada keeli, mis on kas regulaarsed või kontekstivabad. See võimaldab vastava etapi kirjeldada lähteteksti ühekordse vasakult-paremale läbivaatamisena, kusjuures ajaduse korral vaatatakse enne mingi teisenduse tegemist käsitletavast sümbolist ka paar eespool tulevat sümbolit (nn look-ahead) ja seega sooritada vastava etappi (peaaegu) lineaarse kiirusega, s.t. nii, et programmi töötaktide arv on võrdeline sisendteksti pikkusega.

    Ülesandeid:
    1. Mis liiki olid peatükis "Grammatikad" esitatud näidisgrammatikad?
    2. Peatüki "Grammatikad" lõpus on mitmeid ülesandeid grammatika koostamiseks. Analüüsi vastavaid keeli - millised neist on regulaarsed (s.t. keele saab kirjeldada regulaarse grammatikaga), millised kontekstivabad, millised lineaarselt tõkestatud või rekursiivselt loenduvad?
    3. Keel koosneb ühendsüsteemis kirjutatud arvude summadest ja vahedest, s.t. sellesse keelde kuuluks (näiteks) jadad |+|| = |||, |||-| = ||, |+| = ||, || - |||| = -|| jne Kas see keel on regulaarne? Kas see keel on kontekstivaba - kas seda saab tunnistada lõpliku automaadiga? magasinmäluga?
    Küsimused, probleemid: ©2004-2013 Jaak Henno