Teoreetilibe informaatika kordamisküsimused
KV-grammatika, mille korral leidub sõna, millel on mitu tuletuspuud, nimetatakse
mitmeseks.
Teatud mitmestele grammatikatele leidub ekvivalentseid üheseid grammatikaid.
KV keelt, millel leidub ühene genereeriv grammatika, nimetatakse üheseks, millel
ei leidu, mitmeseks.
KV-grammatika G on ühene, kui ei leidu keelde kuuluvaid sõnu, mille erinevad
vasak-, paremtulemused omaksid erinevaid tuletuspuid (mitmene grammatika on
see, mille korral leidub mitu erinevat vasaktuletust).
Vasak- ja paremtuletus.
14. KV-grammatikate redutseerimine.
Keele mittetühjuse kontroll:
IN: KV grammatika G = (,N,P,S)
OUT: Jah/Ei
METHOD:
Koostame hulgad N0,N1,... nii, et:
· N0 = tühi, i=1
· Ni = Ni-1 U {A | A kuulub produktsioonide hulka, ja (Ni-1 U *)}
ehk siis need sõnad, mis saab eelmiste sõnadest produktsioonil ühe
terminaali lisamisega
· Jätkame, kuni lisandub sõnu.
annaabi.ee 
