Ero sivun ”Chomskyn normaalimuoto” versioiden välillä

Wikipediasta
Siirry navigaatioon Siirry hakuun
[arvioimaton versio][arvioimaton versio]
Poistettu sisältö Lisätty sisältö
Rivi 18: Rivi 18:


Olkoon G = {V, Σ P, S) yhteydetön kielioppi. 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.
Olkoon G = {V, Σ P, S) yhteydetön kielioppi. 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.

&epsilon;-produktiot voidaan poistaa seuraavasti: määritellään joukko NULL siten, että siihen kuuluvat kaikki ne kieliopin välikkeet, joista voidaan tuottaa tyhjä merkkijono &epsilon; joko suoraan tai välillisesti. Tämän jälkeen kielioppiin lisätään kaikki sellaiset produktiot, joissa NULL-joukon välikkeet on korvattu epsilonilla. <!--Formaalisti kukin produktio <math>A \rightarrow X_1 X_2 ... X_k</math> korvataan produktiojoukolla <math>A \rightarrow \alpha_1 ... \alpha_k </math>, missä

pitää saada toimimaan: <math>\alpha_i = \left\{\begin{matrix} X_i, & \mbox{jos }X_i\mbox{ \not\in NULL} \\ X_i tai \epsilon & \mbox{jos }X_i\mbox{ \in NULL} \end{matrix}\right. </math>

tähän vielä yksikköproduktioiden poisto -->


Kutakin päätemerkkiä kohden kielioppiin lisätään nyt uusi välike <math>C_a</math> ja produktio <math>C_a \rightarrow a </math>. Korvataan produktioissa esiintyvät päätemerkit näillä uusilla välikkeillä. Nyt kieliopin kaikki produktiot ovat muotoa <math>A\rightarrow a</math> ja <math>A\rightarrow A_1A_2\cdots A_k</math>, <math>k\geq 2</math>. Jälkimmäiseen luokkaan kuuluvat produktiot, joissa <math>k\geq 3</math>, korvataan nyt seuraavilla uusilla produktioilla: <math>A\rightarrow A_1B_1</math>, <math>B_i\rightarrow A_{i+1}B_{i+1}</math> kaikilla <math>i\in\{1,\cdots,k-2\}</math> ja <math>B_{k-1}\rightarrow A_{k-1}A_k</math>. Tässä <math>B_1,\cdots,B_{k-1}</math> 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.
Kutakin päätemerkkiä kohden kielioppiin lisätään nyt uusi välike <math>C_a</math> ja produktio <math>C_a \rightarrow a </math>. Korvataan produktioissa esiintyvät päätemerkit näillä uusilla välikkeillä. Nyt kieliopin kaikki produktiot ovat muotoa <math>A\rightarrow a</math> ja <math>A\rightarrow A_1A_2\cdots A_k</math>, <math>k\geq 2</math>. Jälkimmäiseen luokkaan kuuluvat produktiot, joissa <math>k\geq 3</math>, korvataan nyt seuraavilla uusilla produktioilla: <math>A\rightarrow A_1B_1</math>, <math>B_i\rightarrow A_{i+1}B_{i+1}</math> kaikilla <math>i\in\{1,\cdots,k-2\}</math> ja <math>B_{k-1}\rightarrow A_{k-1}A_k</math>. Tässä <math>B_1,\cdots,B_{k-1}</math> 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.

Versio 21. lokakuuta 2005 kello 06.18

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

ABC
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. 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. Tämän jälkeen kielioppiin lisätään kaikki sellaiset produktiot, joissa NULL-joukon välikkeet on korvattu epsilonilla.

Kutakin päätemerkkiä kohden kielioppiin lisätään nyt uusi välike ja produktio . Korvataan produktioissa esiintyvät päätemerkit näillä uusilla välikkeillä. Nyt kieliopin kaikki produktiot ovat muotoa ja , . Jälkimmäiseen luokkaan kuuluvat produktiot, joissa , korvataan nyt seuraavilla uusilla produktioilla: , kaikilla ja . Tässä 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.