Formaali kielioppi

Wikipedia

Formaali kielioppi on tietojenkäsittelytieteessä rakenne, joka kuvaa tarkasti formaalin kielen. 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.

Sisällysluettelo

1 Generatiiviset kieliopit

[muokkaa] 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:

$S \longrightarrow aSb$
$S \longrightarrow ba$

tai lyhyemmin

$S \longrightarrow aSb | ba$

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: $S \longrightarrow aSb \longrightarrow aaSbb \longrightarrow aababb$ . Kieliopin tuottama kieli on niiden merkkijonojen joukko, jotka voidaan tuottaa kieliopista tällä tavoin: {ba, abab, aababb, aaababbb, ...}.

[muokkaa] 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 $(\Sigma \cup N)^{*}$ merkkijono $\longrightarrow$ joukon $(\Sigma \cup N)^{*}$ merkkijono

(missä

*

on Kleenen tähti ja $\cup$ 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).

[muokkaa] Esimerkki

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

$S \longrightarrow aBSc | abc$
$Ba \longrightarrow aB$
$Bb \longrightarrow bb$

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

$\boldsymbol{S} \longrightarrow abc$
$\boldsymbol{S} \longrightarrow aB\boldsymbol{S}c \longrightarrow a\boldsymbol{Ba}bcc \longrightarrow aa\boldsymbol{Bb}cc \longrightarrow aabbcc$
$\boldsymbol{S} \longrightarrow aB\boldsymbol{S}c \longrightarrow aBaB\boldsymbol{S}cc \longrightarrow a\boldsymbol{Ba}Babccc \longrightarrow aaB\boldsymbol{Ba}bccc\longrightarrow aa\boldsymbol{Ba}Bbccc$ $\longrightarrow aaaB\boldsymbol{Bb}ccc \longrightarrow aaa\boldsymbol{Bb}bccc \longrightarrow aaabbbccc$

Kussakin askeleessa korvattu osajono on lihavoitu.

Kielioppi tuottaa kielen $\left \{ a^{n}b^{n}c^{n} | n > 0 \right \}$ . aⁿ 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ä.

[muokkaa] 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.

Automaattiteoria: formaalit kielet ja formaalit kieliopit
Chomskyn hierarkia	Kielioppi	Kieli	Tunnistusautomaatti
luokka 0	Rajoittamaton	Rekursiivisesti numeroituva	Turingin kone
	Rajoittamaton	Rekursiivinen	Totaalinen Turingin kone
luokka 1	Yhteysherkkä	Yhteysherkkä	Lineaarisesti rajoitettu
luokka 2	Yhteydetön	Yhteydetön	Pinoautomaatti
luokka 3	Säännöllinen	Säännöllinen	Äärellinen
Kukin luokka on sen yläpuolisen luokan aito osajoukko.