Postać normalna Greibach

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

A\rightarrow aX

Gdzie a to dowolny symbol terminalny, X zaś to (być może pusty) ciąg symboli nieterminalnych.

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

S\rightarrow \lambda

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 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.

W oryginalnym zamyśle Greibach w jej artykule przedstawiającym postać z roku 1965 autorka pisze:

Quote-alpha.png
"A context-free phrase structure generator is in standard form if and only if all of its rules are of the form: Z\rightarrow aY_1, . . . , Y_m where Z and Y_i are intermediate symbols and a is a terminal symbol, so that one input symbol is processed at each step..."

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 ekwiwalentnej postaci normalnej Greibach.

Nazwa wywodzi się od Sheili Greibach.

Konstrukcja[edytuj | edytuj kod]

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 A_i \, , 1 {\le} i {\le} n, gdzie 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[edytuj | edytuj kod]

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

Zastąpienie reguł lewostronnie rekursywnych[edytuj | edytuj kod]

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 A_i dla którego istnieją reguły lewostronnie rekursywne. Omawiana operacja pozbędzie się jednocześnie wszystkich reguł lewostronnie rekursywnych mających A_i po lewej stronie. Wprowadzamy nowy symbol nieterminalny, powiedzmy B_i, który nie jest jeszcze elementem danej gramatyki. Z każdej reguły lewostronnie rekursywnej mającej A_i po lewej stronie powstaną dwie produkcje:

produkcja 1: mająca nowo wprowadzony symbol B_i po lewej stronie, a po prawej pozostałość reguły rekursywnej bez pierwszego symbolu (A_i), za to na samym końcu ten nowo wprowadzony symbol nieterminalny B_i;

produkcja 2: jak produkcja pierwsza, ale bez ostatniego symbolu 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 A_i dodajemy dodatkowo reguły z nowo wprowadzonym symbolem 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 A_2 mieliśmy w gramatyce reguły

A_2\rightarrow A_2A_3A_3 | A_2A_2 | aA_3,

to zostaną one zastąpione przez:

B_2\rightarrow A_3A_3B_2 | A_2B_2 (zgodnie z produkcją 1.)
B_2\rightarrow A_3A_3 | A_2 (zgodnie z produkcją 2.)

oraz

A_2\rightarrow aA_3 (pozostaje bez zmian)
A_2\rightarrow aA_3B_2 (z dodanym B_2)

Reguły rekursywne A_2\rightarrow A_2A_3A_3 i A_2 \rightarrow A_2A_2 zostały usunięte.

Kolejność wykonywania operacji[edytuj | edytuj kod]

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 A_1 do A_{i-1}, natomiast dla A_i mamy regułę, w której pierwszy symbol po prawej stronie to jeden spośród 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 A_1,\dots,A_{i-1}. Nadal jednak może to być A_i. Aby wyeliminować tą możliwość stosujemy drugą operację (zastąpienie reguł lewostronnie rekursywnych). Po jej zastosowaniu wszystkie reguły dla A_i mają jako pierwszy symbol prawej strony albo symbol terminalny albo symbol nieterminalny o numerze większym niż i; możemy więc przejść do poprawiania reguł dla A_{i+1}. Zwróćmy uwagę, że nowo wprowadzone symbole B_i nie pojawią na początku prawej strony żadnej reguły.

W przykładowej gramatyce o formie:

A_1\rightarrow A_2A_3 | a
A_2\rightarrow A_1A_3 | A_2A_2
A_3\rightarrow A_2A_1 | b

najpierw podstawiamy za A_1 w regule A_2\rightarrow A_1A_3, następnie eliminujemy reguły lewostronnie rekursywne dla A_2, a następnie podstawiamy za A_2 w regule A_3\rightarrow A_2A_1. Gramatyka przyjmie po tym etapie poniższą postać:

B_2\rightarrow A_3A_3B_2 | A_2B_2 | A_3A_3 | A_2
A_1\rightarrow A_2A_3 | a
A_2\rightarrow aA_3 | aA_3B_2
A_3\rightarrow aA_3A_1 | aA_3B_2A_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ą A_n, idąc poprzez A_i o coraz mniejszych numerach, a na koniec obsługując wszystkie 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 B_i a po prawej 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 A_2 i A_3 są już w docelowej postaci. Pierwszą regułą, którą powinniśmy obsłużyć, jest A_1\rightarrow A_2A_3. Zastępujemy ją przez

A_1\rightarrow aA_3A_3 | aA_3B_2A_3 | a.

Na koniec reguły dla B_2 zastępujemy przez

B_2\rightarrow aA_3A_1A_3B_2 | aA_3B_2A_1A_3B_2 | bA_3B_2 | aA_3B_2 | aA_3B_2B_2 | aA_3A_1A_3 | aA_3B_2A_1A_3 | bA_3 | aA_3 | aA_3B_2.

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

Bibliografia[edytuj | edytuj kod]

  • 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

Zobacz też[edytuj | edytuj kod]