Postać normalna Greibach

Postać normalna Greibach to postać gramatyki bezkontekstowej, w której wszystkie reguły są postaci:

${\displaystyle A\rightarrow aY_{1}...Y_{m},}$

gdzie ${\displaystyle a}$ to dowolny symbol terminalny, ${\displaystyle Y_{1}...Y_{m}}$ to (być może pusty) ciąg symboli nieterminalnych.

Specjalny przypadek produkcji gramatyki typu 1 i wyżej stanowi produkcja

${\displaystyle S\rightarrow \varepsilon }$

generująca wyraz pusty. Produkcja ta nie jest objęta formalną definicją gramatyki bezkontekstowej, która stwierdza, że prawa strona dowolnej produkcji nie może być krótsza niż lewa strona (monotoniczność), a co w tym konkretnym aspekcie ma miejsce. Produkcja ta jest dopuszczalna pod warunkiem, że symbol startowy ${\displaystyle S}$ nie występuje po prawej stronie żadnej produkcji danej gramatyki. W postaci normalnej Chomsky’ego, która stanowi podstawę dla postaci normalnej Greibach, produkcja ta zostaje przejęta bez zmian, ponieważ, wychodząc z założenia, że gramatyka nie zawiera symbolu startowego po prawej stronie, produkcja ta nie może zostać użyta w żadnej innej konfiguracji.

Nazwa wywodzi się od Sheili Greibach. W pierwotnym zamyśle w artykule definiującym tę postać normalną z roku 1965 autorka pisze:

skąd wynika, że ten specjalny przypadek produkcji nie jest zawarty w postaci. Niektóre definicje postaci obejmują jednak również i tę produkcję.

Każdą gramatykę bezkontekstową można przedstawić w postaci normalnej Greibach.

Konstrukcja

Zakładając, że dana gramatyka bezkontekstowa znajduje się już w postaci normalnej Chomsky’ego, pokażemy jak można przetransformować ją do postaci normalnej Greibach. Najpierw, wszystkie symbole nieterminalne danej gramatyki ponumerujmy np. do formy ${\displaystyle A_{i}\,,1{\leq }i{\leq }n,}$ gdzie ${\displaystyle n}$ to liczba symboli nieterminalnych występujących w danej gramatyce. Postać normalną Greibach można uzyskać za pomocą dwóch operacji stosowanych w odpowiedniej kolejności:

Podstawienie za pierwszy symbol po prawej

Aby zastosować tę operację, koncentrujemy naszą uwagę na pewnej regule, w której pierwszy symbol po prawej stronie jest symbolem nieterminalnym, nazwijmy go ${\displaystyle A_{i}.}$ Zastąpimy tę regułę wieloma regułami, po jednej dla każdej reguły mającej ${\displaystyle A_{i}}$ po lewej stronie: w naszej oryginalnej regule wymieniamy to pierwsze ${\displaystyle A_{i}}$ na rezultat zastosowania tej drugiej reguły. Przykładowo, jeśli wszystkie reguły z ${\displaystyle A_{1}}$ po lewej stronie to ${\displaystyle A_{1}\rightarrow A_{2}A_{3}}$ i ${\displaystyle A_{1}\rightarrow a,}$ to regułę ${\displaystyle A_{2}\rightarrow A_{1}A_{3}}$ możemy zastąpić regułami ${\displaystyle A_{2}\rightarrow A_{2}A_{3}A_{3}}$ i ${\displaystyle A_{2}\rightarrow aA_{3}.}$ Zwróćmy uwagę, że taka zamiana nie zmienia języka generowanego przez gramatykę.

Zastąpienie reguł lewostronnie rekursywnych

Pod określeniem reguły lewostronnie rekursywnej rozumiane są tutaj produkcje, gdzie pierwszy symbol po prawej stronie jest taki sam jak symbol po lewej stronie. Ustalmy symbol nieterminalny ${\displaystyle A_{i}}$ dla którego istnieją reguły lewostronnie rekursywne. Omawiana operacja pozbędzie się jednocześnie wszystkich reguł lewostronnie rekursywnych mających ${\displaystyle A_{i}}$ po lewej stronie. Wprowadzamy nowy symbol nieterminalny, powiedzmy ${\displaystyle B_{i},}$ który nie jest jeszcze elementem danej gramatyki. Z każdej reguły lewostronnie rekursywnej mającej ${\displaystyle A_{i}}$ po lewej stronie powstaną dwie produkcje:

produkcja 1: mająca nowo wprowadzony symbol ${\displaystyle B_{i}}$ po lewej stronie, a po prawej pozostałość reguły rekursywnej bez pierwszego symbolu ${\displaystyle (A_{i}),}$ za to na samym końcu ten nowo wprowadzony symbol nieterminalny ${\displaystyle B_{i};}$

produkcja 2: jak produkcja pierwsza, ale bez ostatniego symbolu ${\displaystyle B_{i}.}$

Reguła rekursywna zostaje przy tym usunięta z gramatyki. Do wszystkich innych (czyli tych, które nie są lewostronnie rekursywne) reguł posiadających po lewej stronie symbol ${\displaystyle A_{i}}$ dodajemy dodatkowo reguły z nowo wprowadzonym symbolem ${\displaystyle B_{i}}$ na samym końcu. Można zauważyć, że opisana operacja nie zmienia języka generowanego przez gramatykę.

Przykładowo, jeśli dla ${\displaystyle A_{2}}$ mieliśmy w gramatyce reguły

${\displaystyle A_{2}\rightarrow A_{2}A_{3}A_{3}|A_{2}A_{2}|aA_{3},}$

to zostaną one zastąpione przez:

${\displaystyle B_{2}\rightarrow A_{3}A_{3}B_{2}|A_{2}B_{2}}$ (zgodnie z produkcją 1.).

${\displaystyle B_{2}\rightarrow A_{3}A_{3}|A_{2}}$ (zgodnie z produkcją 2.)

oraz

${\displaystyle A_{2}\rightarrow aA_{3}}$ (pozostaje bez zmian),

${\displaystyle A_{2}\rightarrow aA_{3}B_{2}}$ (z dodanym ${\displaystyle B_{2}}$).

Reguły rekursywne ${\displaystyle A_{2}\rightarrow A_{2}A_{3}A_{3}}$ i ${\displaystyle A_{2}\rightarrow A_{2}A_{2}}$ zostały usunięte.

Kolejność wykonywania operacji

Przekształcanie gramatyki do postaci normalnej Greibach wykonujemy w dwóch etapach. Celem pierwszego etapu jest zapewnienie, że w gramatyce będą wyłącznie reguły, w których pierwszy symbol po prawej stronie jest symbolem nieterminalnym o indeksie wyższym niż indeks lewej strony, bądź jest symbolem terminalnym. Systematycznie przeszukujemy wszystkie reguły gramatyki, zaczynając od tego symbolu nieterminalnego po lewej stronie, który ma najniższy indeks, a kończąc na tym, którego indeks jest najwyższy. Przypuśćmy, że obsłużyliśmy już symbole od ${\displaystyle A_{1}}$ do ${\displaystyle A_{i-1},}$ natomiast dla ${\displaystyle A_{i}}$ mamy regułę, w której pierwszy symbol po prawej stronie to jeden spośród ${\displaystyle A_{1},\dots ,A_{i-1},}$ czyli niezgodnie z naszą docelową postacią. Wówczas w tej regule podstawiamy za pierwszy symbol po prawej stronie (pierwsza operacja powyżej). W wyniku tego dostajemy reguły, w których pierwszy symbol po prawej stronie jest terminalem bądź ma większy numer niż w oryginalnej regule. Powtarzając tę operację możemy zapewnić, że pierwszym symbolem po prawej stronie nie będzie żaden z symboli ${\displaystyle A_{1},\dots ,A_{i-1}.}$ Nadal jednak może to być ${\displaystyle A_{i}.}$ Aby wyeliminować tę możliwość stosujemy drugą operację (zastąpienie reguł lewostronnie rekursywnych). Po jej zastosowaniu wszystkie reguły dla ${\displaystyle A_{i}}$ mają jako pierwszy symbol prawej strony albo symbol terminalny albo symbol nieterminalny o numerze większym niż ${\displaystyle i;}$ możemy więc przejść do poprawiania reguł dla ${\displaystyle A_{i+1}.}$ Zwróćmy uwagę, że nowo wprowadzone symbole ${\displaystyle B_{i}}$ nie pojawią na początku prawej strony żadnej reguły.

W przykładowej gramatyce o formie:

${\displaystyle A_{1}\rightarrow A_{2}A_{3}|a,}$

${\displaystyle A_{2}\rightarrow A_{1}A_{3}|A_{2}A_{2},}$

${\displaystyle A_{3}\rightarrow A_{2}A_{1}|b.}$

najpierw podstawiamy za ${\displaystyle A_{1}}$ w regule ${\displaystyle A_{2}\rightarrow A_{1}A_{3},}$ następnie eliminujemy reguły lewostronnie rekursywne dla ${\displaystyle A_{2},}$ a następnie podstawiamy za ${\displaystyle A_{2}}$ w regule ${\displaystyle A_{3}\rightarrow A_{2}A_{1}.}$ Gramatyka przyjmie po tym etapie poniższą postać:

${\displaystyle B_{2}\rightarrow A_{3}A_{3}B_{2}|A_{2}B_{2}|A_{3}A_{3}|A_{2},}$

${\displaystyle A_{1}\rightarrow A_{2}A_{3}|a,}$

${\displaystyle A_{2}\rightarrow aA_{3}|aA_{3}B_{2},}$

${\displaystyle A_{3}\rightarrow aA_{3}A_{1}|aA_{3}B_{2}A_{1}|b.}$

W drugim etapie systematycznie zastępujemy wszystkie reguły zaczynające się po prawej stronie symbolem nieterminalnym. Zaczynamy przy tym od produkcji, które po lewej mają ${\displaystyle A_{n},}$ idąc poprzez ${\displaystyle A_{i}}$ o coraz mniejszych numerach, a na koniec obsługując wszystkie ${\displaystyle B_{i}.}$ Gdy obsługujemy jakąś regułę, to numer pierwszego symbolu po prawej stronie jest większy niż numer lewej strony albo po lewej mamy ${\displaystyle B_{i},}$ a po prawej ${\displaystyle A_{i}),}$ 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 ${\displaystyle A_{2}}$ i ${\displaystyle A_{3}}$ są już w docelowej postaci. Pierwszą regułą, którą powinniśmy obsłużyć, jest ${\displaystyle A_{1}\rightarrow A_{2}A_{3}.}$ Zastępujemy ją przez

${\displaystyle A_{1}\rightarrow aA_{3}A_{3}|aA_{3}B_{2}A_{3}|a.}$

Na koniec reguły dla ${\displaystyle B_{2}}$ zastępujemy przez

${\displaystyle B_{2}\rightarrow aA_{3}A_{1}A_{3}B_{2}|aA_{3}B_{2}A_{1}A_{3}B_{2}|bA_{3}B_{2}|aA_{3}B_{2}|aA_{3}B_{2}B_{2}|aA_{3}A_{1}A_{3}|aA_{3}B_{2}A_{1}A_{3}|bA_{3}|aA_{3}|aA_{3}B_{2}.}$

Gramatyka znajduje się w całości w postaci normalnej Greibach.

Zobacz też

• postać normalna Chomsky’ego

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, ​ISBN 3-8274-1099-1​, strony 54-57