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.

Muilla kielillä