Ero sivun ”Chomskyn normaalimuoto” versioiden välillä

Siirry navigaatioon Siirry hakuun
15 merkkiä poistettu ,  16 vuotta sitten
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{;X_i \not\in \mbox{NULL} \\ X_i \;\mbox{tai}\; \epsilon & \mbox{jos }X_i\mbox{; X_i \in \mbox{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.
19 626

muokkausta

Navigointivalikko