Chomskyn normaalimuoto

Wikipedia
Loikkaa: valikkoon, hakuun

Tietojenkäsittelytieteessä formaali kielioppi on Chomskyn normaalimuodossa jos ja vain jos sen kaikki produktiot ovat muotoa

A → BC
A → α tai
S → ε

missä A, B ja C ovat välikkeitä, α on päätemerkki, S lähtösymboli ja ε tyhjä merkkijono. Kieliopin välikkeistä vain S saa olla tyhjentyvä eli tuottaa tyhjän merkkijonon.

Ominaisuuksia[muokkaa | muokkaa wikitekstiä]

Jokainen Chomskyn normaalimuodossa oleva kielioppi on yhteydetön, ja kääntäen jokainen yhteydetön kielioppi voidaan muuttaa Chomskyn normaalimuotoon. Chomskyn normaalimuodossa olevassa kieliopissa merkkijonon pituus kasvaa jokaisessa johdon askelessa yhdellä, minkä vuoksi n merkkiä pitkän merkkijonon johto on aina 2n-1 askelta. Koska lisäksi kieliopissa yhden välikkeen voi korvata täsmälleen kahdella muulla välikkeellä, Chomskyn normaalimuodossa olevan kieliopin jäsennyspuut ovat binääripuita, joiden korkeus on enintään merkkijonon pituus.

Näiden ominaisuuksien muoksi monet tietojenkäsittelyteorian sovellukset hyödyntävät Chomskyn normaalimuotoa. Esimerkiksi CYK-algoritmi, joka ratkaisee voidaanko annettu merkkijono tuottaa kieliopista vai ei, edellyttää kieliopin olevan Chomskyn normaalimuodossa.

Chomskyn normaalimuoto on nimetty kielitieteilijä Noam Chomskyn mukaan, joka keksi myös Chomskyn hierarkian.

Kieliopin muuttaminen Chomskyn normaalimuotoon[muokkaa | muokkaa wikitekstiä]

Olkoon G = {V, Σ, P, S) yhteydetön kielioppi. Chomskyn normaalimuodossa lähtösymboli S ei saisi esiintyä minkään produktion oikealla puolella. Tämän poistamiseksi otetaan käyttöön uusi lähtösymboli S' ja kirjoitetaan uusi produktio S' → S. Tämän jälkeen G:stä poistetaan kaikki ε-produktiot ja yksikköproduktiot eli sellaiset produktiot, joissa välike tuottaa ainoastaan yhden muun välikkeen.

  • ε-produktiot voidaan poistaa seuraavasti: määritellään joukko NULL siten, että siihen kuuluvat kaikki ne kieliopin välikkeet, joista voidaan tuottaa tyhjä merkkijono ε joko suoraan tai välillisesti (siis ne välikkeet X, joille X →* ε). Tämän jälkeen kielioppiin lisätään kaikki sellaiset produktiot, joissa NULL-joukon välikkeet on korvattu epsilonilla. Formaalisti kukin produktio A \rightarrow X_1 X_2 ... X_k korvataan kaikkien produktioiden A \rightarrow \alpha_1 ... \alpha_k joukolla, missä \alpha_i =\left\{\begin{matrix} X_i, & \mbox{jos}\;X_i \not\in \mbox{NULL} \\ X_i \;\mbox{tai}\; \epsilon & \mbox{jos}\; X_i \in \mbox{NULL} \end{matrix}\right.
    Lopuksi poistetaan kaikki ε-produktiot (A → ε). Tarvittaessa (jos S → ε) otetaan käyttöön uusi lähtösymboli S' sekä produktiot S' → S ja S' → ε.
  • Tarkastellaan vielä yksikköproduktioiden poistamista. Yksikköproduktiot ovat muotoa A → B, missä A ja B ovat välikkeitä. Muodostetaan ensin kullekin kieliopin välikkeelle yksikköseuraajien joukko F(A). Joukkoon tulevat ne välikkeet, jotka voidaan suoraan tai välillisesti tuottaa välikkeestä A (yksinään, siis kaikki ne välikkeet X, joille A →* X). Tämän jälkeen korvataa kieliopin yksikköproduktiot produktioilla A → ω, missä B → ω on ei-yksikköproduktio jollakin B \in F(A).

Kutakin päätemerkkiä kohden kielioppiin lisätään nyt uusi välike C_a ja produktio C_a \rightarrow a . Korvataan produktioissa esiintyvät päätemerkit näillä uusilla välikkeillä. Nyt kieliopin kaikki produktiot ovat muotoa A\rightarrow a ja A\rightarrow A_1A_2\cdots A_k, k\geq 2. Jälkimmäiseen luokkaan kuuluvat produktiot, joissa k\geq 3, korvataan nyt seuraavilla uusilla produktioilla: A\rightarrow A_1B_1, B_i\rightarrow A_{i+1}B_{i+1} kaikilla i\in\{1,\cdots,k-2\} ja B_{k-1}\rightarrow A_{k-1}A_k. Tässä B_1,\cdots,B_{k-1} ovat uusia välikkeitä. Enemmän kuin kaksi välikettä tuottavien produktioiden oikeat puolet pilkotaan siis kahden välikkeen pituisiin osiin, jotka nimetään omiksi välikkeikseen, ja kielioppiin lisätään uusia välikkeitä vastaavat produktiot.