Teoreetilibe informaatika kordamisküsimused
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.
Iga KV keel on genereeritav mitte-vasakrekursiivse grammatikaga.
Teisendamine Greibachi normaalkujule:
· Vasakrekursiooni elimineerimine (redutseeritud grammatika sisendiks)
· Grammatika viimine greibachi normaalkujule
Näide:
annaabi.ee 
