Zaczynamy przy tym od produkcji, które po lewej mają idąc poprzez o coraz mniejszych numerach, a na koniec obsługując wszystkie Gdy obsługujemy jakąś regułę, to numer pierwszego symbolu po prawej stronie jest większy niż numer lewej strony albo po lewej mamy a po prawej czyli wszystkie reguły dla pierwszego symbolu po prawej stronie zostały już przetworzone i ich prawe strony zaczynają się od symbolu terminalnego. Zatem jednokrotne zastosowanie operacji podstawienia za pierwszy symbol po prawej stronie spowoduje, że dostaniemy wyłącznie reguły, których prawa strona zaczyna się od symbolu terminalnego. Po obsłużeniu w ten sposób wszystkich reguł dostajemy gramatykę w postaci normalnej Greibach.
W naszej przykładowej gramatyce reguły dla i są już w docelowej postaci. Pierwszą regułą, którą powinniśmy obsłużyć, jest Zastępujemy ją przez
Na koniec reguły dla zastępujemy przez
Gramatyka znajduje się w całości w postaci normalnej Greibach.
Zobacz też postać normalna Chomskiego
Bibliografia Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the Association for Computing Machinery, 1965, Vol. 12, No.1, strony 42-52 Uwe Schöning, Theoretische Informatik – kurzgefasst, Spektrum Akademischer Verlag, 1994, , strony 54-57
Kategoria:Języki formalne