Teoreetilibe informaatika kordamisküsimused
= N U {S'}, vastasel juhul N' = N
· G' = {,N',P',S'}
Ahelproduktsioonide elimineerimine:
IN: KV grammatika G = (,N,P,S)
OUT: Ekvivalentne KV grammatika G', milles pole ahelprduktsioone
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:
annaabi.ee 
