Forma normală Greibach
Acest articol nu are introducere cu explicația scurtă a subiectului sau introducerea existentă este prea scurtă. Puteți să o adăugați sau să o extindeți. |
Acest articol sau această secțiune nu este î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