Ero sivun ”Chomskyn normaalimuoto” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Ei muokkausyhteenvetoa |
|||
Rivi 17:
==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.
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.
[[Luokka:Formaalit kielet]]
| |||