Teoreetilibe informaatika kordamisküsimused
METHOD:
· Iga mitteterminaali A jaoks konstrueerime hulga N A = {A | A =>* B}, kus:
o N0 = {A}, i = 1
o Ni = Ni-1 U {C | B C on produktsioon, B kuulub Ni}
need A-st tuletatavad mitteterminaalid, millest ei saa
produktsioonides terminaale
o Kui lisandus elemente, teeme veelkorra, kui ei N A = Ni
· Konstrueerime hulga P', millesse lisame järgmiselt:
o kui produktsioonid B pole ahelproduktsioon, lisame P'-sse A
kõigi selliste mitteterminaalide A jaoks, mille korral B kuulus N A
Ehk siis .. lisame uue grammatika produktsioonideks need, mille korral
mitte-ahelproduktsioon B ei saa ahelproduktsiooniks
Redutseeritud grammatika definitsioon:
KV grammatikat G = (,N,P,S) nimetatakse redutseerituks, kui see ei sisalda
tsükleid, -reegleid ja kasutuid sümboleid.
Iga KV keele jaoks leidub genereeriv redutseeritud grammatika.
15
annaabi.ee 
