Forma normală Greibach

De la Wikipedia, enciclopedia liberă

[[wiki]]

Acest articol sau această secţiune trebuie pus(ă) în formatul standard. Ştergeţi eticheta la încheierea standardizării. Acest articol a fost etichetat în 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 :

cu

şi