Vizualizare sursă pentru „Forma normală Greibach”

{{fără introducere|date=septembrie 2016}}
{{Wikizare-dată|august 2006}}
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 :

::<math>A \to a x</math>

cu
::<math>a \ \epsilon  T</math> 
și
::<math>x \epsilon N^*</math>



[[Categorie:Limbaje formale și automate]]