Formaali kielioppi

Formaali kielioppi on  rakenne, joka kuvaa tarkasti formaalin kielen. Käsitettä käytetään niin tietojenkäsittelytieteessä kuin kielitieteessäkin. Yleensä kielioppi on joukko sääntöjä, joka tuottaa (yleensä äärettömän) joukon äärellisen pituisia merkkijonoja (yleensä äärellisestä) aakkostosta. Formaalin kieliopin nimitys on analogia luonnollisten kielten kieliopeille.

Formaalit kieliopit voidaan jakaa kahteen pääluokkaan: generatiivisiin ja analyyttisiin.

 Generatiivinen kielioppi on tunnetuin tyyppi formaalista kieliopista. Se on joukko sääntöjä, jotka määrittelevät kaikki kieliopin tuottamaan formaaliin kieleen kuuluvat merkkijonot. Näin kaikki kieleen kuuluvat merkkijonot voidaan tuottaa (generoida) kirjoittamalla osajonoja toistuvasti uudelleen kieliopin sääntöjen mukaisesti tietystä lähtösymbolista alkaen. Generatiivinen kielioppi on siis algoritmi, joka tuottaa kaikki kielen merkkijonot.

 Analyyttinen kielioppi puolestaan on joukko sääntöjä, jolle annetaan syötteenä mielivaltainen merkkijono. Kielioppi tuottaa lopulta totuusarvoisen ("kyllä/ei") tuloksen, joka kertoo kuuluuko annettu merkkijono kieliopin kuvaamaan kieleen. Analyyttinen kielioppi määrittelee siis kielen jäsentäjän.

Generatiiviset kieliopit

Generatiivinen kielioppi koostuu joukosta sääntöjä, joilla merkkijonoja voidaan kirjoittaa uudelleen eli muuttaa toisiksi merkkijonoiksi. Jonon tuottaminen alkaa yksittäisestä lähtösymbolista, johon kieliopin sääntöjä sovelletaan mielivaltaisen monta kertaa. Kieli koostuu kaikista niistä merkkijonoista, jotka voidaan tuottaa tällä tavoin. Jos saman merkkijonon voi tuottaa monella eri tavalla eli useammalla kuin yhdellä produktiojonolla, kieliopin sanotaan olevan moniselitteinen.

Otetaan esimerkkinä kielioppi, jonka aakkosto on {a, b}, lähtösymboli S ja johon sisältyvät seuraavat säännöt:

 
 

tai lyhyemmin

 

Aloitamme lähtösymbolista S ja valitsemme siihen sovellettavan säännön. Jos valitaan sääntö 1, S korvataan merkkijonolla aSb. Jos nyt sovelletaan uudemman kerran sääntöä 1, saadaan tulokseksi aaSbb. Tätä prosessia toistetaan kunnes tuloksena on ainoastaan aakkoston merkeistä a ja b (päätemerkeistä) koostuva merkkijono. Voimme esimerkiksi soveltaa jonoon aaSbb sääntöä 2, jolloin lopullinen merkkijono on aababb. Prosessin voi kirjoittaa lyhyemmin: . Kieliopin tuottama kieli on niiden merkkijonojen joukko, jotka voidaan tuottaa kieliopista tällä tavoin: {ba, abab, aababb, aaababbb, ...}.

Formaali määritelmä

Ensimmäisessä Noam Chomskyn ehdottamassa formalisaatiossa generatiivinen kielioppi koostuu seuraavista komponenteista:

 N, äärellinen joukko välikkeitä
 Σ, äärellinen joukko päätemerkkejä
 P, äärellinen joukko produktioita, jotka ovat muotoa
 joukon  merkkijono  joukon  merkkijono 

(missä  on Kleenen tähti ja  on yhdiste sillä rajoituksella, että produktion vasemman puolen tulee sisältää ainakin yksi välike)

 S, lähtösymboli (N:n alkio)

Yleensä tällainen kielioppi esitetään nelikkona (N, Σ P, S). Kieliopin G tunnistamaa kieltä merkitään L(G).

Esimerkki 

Määritellään kielioppi G siten, että N = {S, B}, Σ = {a, b, c}, P koostuu seuraavista produktioista

 
 
 

ja välike S on lähtösymboli. Joitakin esimerkkejä kielen L(G) merkkijonojen tuottamisesta

 
 
 

Kussakin askeleessa korvattu osajono on lihavoitu.

Kielioppi tuottaa kielen . an tarkoittaa merkkijonoa, jossa on peräkkäin n kappaletta a:ta. Siten kieli koostuu merkkijonoista, joissa on jokin positiivinen määrä merkkejä a, niitä seuraa saman verran merkkejä b ja edelleen sama määrä merkkejä c tässä järjestyksessä.

Chomskyn hierarkia 

Kun Noam Chomsky ensimmäisen kerran formalisoi generatiiviset kieliopit 1950-luvulla, hän jakoi ne neljän luokkaan (ns. Chomskyn hierarkia). Mitä suurempaan luokkaan mennään, sitä rajoittuneempi on kielioppi ja sitä vähemmän formaaleja kieliä kieliopilla voidaan tuottaa. Esimerkkejä Chomskyn luokista ovat yhteydettömät ja säännölliset kieliopit. Vastaavasti näillä kieliopeilla voidaan kuvata yhteydettömät ja säännölliset kielet. Vaikka nämä luokat ovat ilmaisuvoimaltaan paljon rajoittuneempia kuin rajoittamattomat kieliopit, jotka voivat kuvata minkä tahansa Turingin koneen tunnistaman kielen, käytetään pienempiä luokkia useammin koska niille voidaan toteuttaa jäsentäjät tehokkaasti.

Formaalit kielet