Teoreetilibe informaatika kordamisküsimused
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.
Iga KV keel on genereeritav mitte-vasakrekursiivse grammatikaga.
Teisendamine Greibachi normaalkujule:
· Vasakrekursiooni elimineerimine (redutseeritud grammatika sisendiks)
· Grammatika viimine greibachi normaalkujule
Näide:
· Seame sisse mitteterminaalide järjestus nii, et järjestuses vasakul
paiknevad oleksid ka produktsioonides pigem vasakul
· Hakkan järjestuse vasakult vaatama produktsioone, mis evivad antud
mitteterminaali vasakus pooles
o kui selles produktsioonis pole vastuolusid mitteterminaalide
järjestusega, jäävad
annaabi.ee 
