Forma normală Greibach

De la Wikipedia, enciclopedia liberă

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 gramatica 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 aceasta 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 \alpha X 

cu

       a \ \epsilon  T 

şi

       \alpha \ \epsilon N^*