Chomskyn normaalimuoto

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

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

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 korvataan 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_{1}A_{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_{1}B_{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.