Ero sivun ”Chomskyn normaalimuoto” versioiden välillä

1 112 merkkiä lisätty ,  16 vuotta sitten
 
==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]]
19 626

muokkausta