Ero sivun ”Chomskyn normaalimuoto” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Rivi 19:
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. Formaalisti kukin produktio <math>A \rightarrow X_1 X_2 ... X_k</math> korvataan kaikkien produktioiden <math>A \rightarrow \alpha_1 ... \alpha_k </math> joukolla, missä <math>\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.</math> <br>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 <math>\in</math> F(A).
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.
| |||