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. KV-grammatikate normaalkujud. Chomsky normaalkuju: KV-grammatika G = (,N,P,S) öeldakse olevat Chomsky normaalkujul, kui see sisldab produktsioone järgnevatel kujudel: A BC (kõik on mitteterminaalid) A b (b on terminaal, a mitteterminaal) S (S on lähtesümbol, mis ei esine ühegi produktsiooni paremas pooles) Iga KV grammatika evib Chomsky normaalkuju. Chomsky normaalkuju korral on sõna tuletuspuuks kahendpuu. Greibachi normaalkuju: -vaba KV grammatika on Graibachi normaakujul, kui kõik produktsioonid (va S ) on kujul A a, kus a on terminaal ja on mitteterminaal Mitteterminaali nimetatakse rekursiivseks, kui A =>+ A. Kui = , siis vasakrekursiivne.
tuletatav α + β kui α-st saab β k sammuga, kirjutatakse α k β; kui α = β või α + β , kirjutatakse α ∗ β DEF: α ∗ β, kui mingi k ∈ {0, 1, 2, . . .} korral α k β. 8 KV keeled. KV keelte ühesus. DEF: Kontekstivabaks grammatikaks (KV) nimetatakse nelikut G = (N,Σ,P,S), kus N on mitteterminaalide tähestik, Σ on terminaalide tähestik (neil pole ühisosa), P ⊆ N×(N∪Σ)* on produktsioonide lõplik hulk, S on lähtesümbol (mitteterminaal). DEF: KV grammatikaga G = (N,Σ,P,S) genereeritav keel on sõnede hulk L(G)={ x | S * x ning x ∈Σ* } (iga x, mis kuulub terminaalide tähestikku ja on produtseeritav lähtesümbolist). DEF: Sõnede hulk L on KV keel, kui leidub KV grammatika G, nii et L=L(G). DEF: KV-grammatika G on ühene, kui iga sõne x ∈ L(G) korral leidub ainult 1 tuletuspuu (1 vasaktuletus). DEF: KV-keel L on ühene, kui kui leidub ühene KV-grammatika G , nii et L = L(G). Teoreem: Olgu L1 ja L2 ühesed keeled
annaabi.ee 
