Forma normală Greibach

Format:Fără introducere Format:Wikizare-dată O gramatică independentă de context pentru care este îndeplinită condiția ca partea dreaptă a oricărei producții începe cu un terminal sau este șirul vid se numește gramatică de tip Q.

O formă particulară de gramatică de tip Q este forma normală Greibach. În acest caz nu există λ-producții cu excepția cel mult a unei λ-producții corespunzătoare simbolului de start al gramaticii. În cazul în care această producție există, simbolul de start al gramaticii nu apare în partea dreaptă a nici unei producții.

În forma normală Greibach producțiile sunt de forma :

$A\to ax$

cu

$aϵT$

și

$xϵN^{*}$