Postać normalna Greibach

Postać normalna Greibach

Postać normalna Greibach (GNF) to specyficzna forma gramatyki bezkontekstowej. W tej formie reguły mają postać:

$A\; \backslash rightarrow\; aY\_1\dots Y\_m$,

gdzie $a$ jest symbolem terminalnym, a $Y\_1\dots Y\_m$ to ciąg symboli nieterminalnych (może być pusty). Wyjątkową regułą jest $S\; \backslash rightarrow\; \backslash varepsilon$, generująca wyraz pusty, która jest dozwolona, jeżeli symbol startowy $S$ nie występuje po prawej stronie żadnej produkcji.

Konstrukcja postaci normalnej Greibach

Aby przekształcić gramatykę bezkontekstową w GNF, zakładamy, że znajduje się ona w postaci normalnej Chomsky’ego. Proces ten można zrealizować w dwóch głównych etapach:

1. Podstawienie za pierwszy symbol po prawej

Wybieramy regułę, w której pierwszy symbol po prawej stronie jest nieterminalny, nazwijmy go $A\_i$. Zastępujemy go nowymi regułami, które odpowiadają wszystkim regułom z $A\_i$ po lewej stronie. Przykładowo, dla reguły $A\_1\; \backslash rightarrow\; A\_2A\_3$, jeśli $A\_2\; \backslash rightarrow\; a$, to zamieniamy $A\_1$ na odpowiednie reguły.

2. Zastąpienie reguł lewostronnie rekursywnych

Reguły lewostronnie rekursywne to te, gdzie pierwszy symbol po prawej stronie jest taki sam jak po lewej. Wprowadzamy nowy symbol nieterminalny $B\_i$, tworząc dwie produkcje z reguł rekursywnych, a następnie usuwamy pierwotne reguły rekursywne. Przykład:

• $A\_2\; \backslash rightarrow\; A\_2A\_3\; |\; a$ staje się $B\_2\; \backslash rightarrow\; A\_3B\_2\; |\; aB\_2$ oraz $A\_2\; \backslash rightarrow\; a$.

Kolejność wykonywania operacji

Przekształcanie gramatyki w GNF wykonujemy w dwóch etapach. Pierwszy etap zapewnia, że reguły mają pierwszy symbol po prawej stronie jako terminalny bądź nieterminalny o wyższym indeksie. W drugim etapie przetwarzamy reguły, zaczynając od tych z najwyższym indeksem, aby upewnić się, że prawa strona każdej reguły zaczyna się od symbolu terminalnego.

W rezultacie, po zastosowaniu obu etapów, gramatyka osiąga postać normalną Greibach, co umożliwia jej efektywne wykorzystanie w różnych zastosowaniach w teorii języków formalnych oraz automatyce.