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, można przetransformować ją do postaci normalnej Greibach za pomocą 3 zasad:

Zastąpienie reguł, w których indeks po lewej stronie jest wyższy niż indeks po prawej[edytuj | edytuj kod]

Wszystkie symbole nieterminalne danej gramatyki numerujemy np. do formy A_i \, , 1 {<} i {<} n, gdzie n to liczba symboli terminalnych występujących w danej gramatyce. Systematycznie przeszukujemy wszystkie reguły gramatyki, zaczynając od tego symbolu nieterminalnego po lewej stronie, który ma najwyższy indeks, a kończąc na tym, którego indeks jest najniższy. Porównujemy przy tym indeks lewej strony z indeksem pierwszego symbolu nieterminalnego po prawej stronie.

W przykładowej gramatyce o formie:

A_1\rightarrow A_2A_3
A_2\rightarrow A_3A_1
A_3\rightarrow A_2A_1 | a

zmianie ulegnie jedynie ostatnia reguła, ponieważ indeks symbolu nieterminalnego po lewej jest wyższy niż indeks pierwszego symbolu nieterminalnego po prawej. W regule tej wymieniamy ten symbol (A_2) na rezultat zastosowania reguły drugiej, czyli A_3A_1. Gramatyka przyjmie po tym kroku poniższą postać:

A_1\rightarrow A_2A_3
A_2\rightarrow A_3A_1
A_3\rightarrow A_3A_1A_1 | a

Jeśli po pierwszej turze zmian gramatyka zawiera jeszcze reguły wymagające wymiany, stosujemy tę zasadę tak długo, aż gramatyka jest wolna od produkcji tego typu.

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

Pod określeniem reguły rekursywnej rozumiane są tutaj produkcje, gdzie symbol po lewej stronie oraz pierwszy symbol po prawej stronie posiadają identyczny indeks. W przypadku wystąpienia takiej reguły w gramatyce, wprowadzamy nowy symbol nieterminalny, który nie jest jeszcze elementem danej gramatyki, oraz dwie produkcje:

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

produkcja 2: jak produkcja pierwsza, ale bez ostatniego symbolu.

Reguła rekursywna zostaje przy tym usunięta z gramatyki.

Do wszystkich innych reguł posiadających po lewej stronie symbol nieterminalny jakiejś reguły rekursywnej dodajemy dodatkowo reguły z nowo wprowadzonym symbolem nieterminalnym na samym końcu. (produkcja 3.)

W rezultacie, reguły z powyższej gramatyki

A_3\rightarrow A_3A_1A_1 | a

zostaną zastąpione przez:

B_3\rightarrow A_1A_1B_3 (zgodnie z produkcją 1.)
B_3\rightarrow A_1A_1 (zgodnie z produkcją 2.)

oraz

A_3\rightarrow a (pozostaje bez zmian)
A_3\rightarrow aB_3 (zgodnie z produkcją 3.)

Reguła rekursywna A_3\rightarrow A_3A_1A_1 została usunięta.

Eliminacja reguł zawierających symbole nieterminalne[edytuj | edytuj kod]

Systematycznie, poczynając od produkcji, które po prawej stronie zaczynają się symbolem terminalnym, zastępujemy wszystkie reguły zaczynające się po prawej stronie symbolem nieterminalnym.

Po zastąpieniu reguł z indeksem po lewej wyższym niż indeks po prawej oraz reguł rekursywnych, gramatyka przedstawiona powyżej składa się z poniższych produkcji:

A_1\rightarrow A_2A_3
A_2\rightarrow A_3A_1
A_3\rightarrow aB_3 | a
B_3\rightarrow A_1A_1B_3 | A_1A_1

Ponieważ produkcje mające A_3 po lewej stronie są już w postaci normalnej Greibach, zastępujemy nimi pozostałe produkcje. Najpierw A_2:

A_2\rightarrow aB_3A_1 | aA_1

następnie A_1:

A_1\rightarrow aB_3A_1A_3 | aA_1A_3

a na samym końcu B_3:

B_3\rightarrow aB_3A_1A_3A_1B_3 | aB_3A_1A_3A_1 | aA_1A_3A_1B_3 | aA_1A_3A_1

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]