Ero sivun ”Chomskyn normaalimuoto” versioiden välillä

51 merkkiä lisätty ,  16 vuotta sitten
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.
 
*&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 (siis ne välikkeet X, joille X &rarr;* &epsilon;). 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 &epsilon;-produktiot (A &rarr; &epsilon;). Tarvittaessa (jos S &rarr; &epsilon;) otetaan käyttöön uusi lähtösymboli S' sekä produktiot S'&nbsp;&rarr;&nbsp;S ja S'&nbsp;&rarr;&nbsp;&epsilon;.
 
*Tarkastellaan vielä yksikköproduktioiden poistamista. Yksikköproduktiot ovat muotoa A &rarr; 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 &rarr;* X). Tämän jälkeen korvataa kieliopin yksikköproduktiot produktioilla A &rarr; &omega;, missä B &rarr; &omega; on ei-yksikköproduktio jollakin B <math>\in</math> F(A).
19 626

muokkausta