Greibach-Normalform

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Greibach-Normalform ist ein Begriff der theoretischen Informatik, der im Zusammenhang mit kontextfreien Sprachen von Interesse ist. Sie ist nach der US-Informatikerin Sheila A. Greibach benannt und beschreibt eine Normalform der kontextfreien Grammatiken. Jede kontextfreie Grammatik, nach der nicht das leere Wort abgeleitet werden kann, kann in eine Greibach-Normalform transformiert werden. Die herausragende Eigenschaft der Greibach-Normalform ist, dass bei jedem Ableitungsschritt jeweils genau ein Terminalzeichen entsteht. Damit ist sie der natürliche Zwischenschritt bei der Umformung einer kontextfreien Grammatik in einen äquivalenten nichtdeterministischen Kellerautomaten ohne -Übergänge.

Eine weitere Normalform für kontextfreie Grammatiken ist die Chomsky-Normalform.

Formale Definition[Bearbeiten | Quelltext bearbeiten]

Sei eine kontextfreie Grammatik (vgl. Chomsky-Hierarchie), also , mit . Dabei sei die Menge der Nichtterminalsymbole, die Menge der Terminalsymbole, die Menge von Produktionsregeln und das Startsymbol. Sei das leere Element .

ist in Greibach-Normalform (kurz GNF), wenn alle Produktionen aus die Form mit haben, wobei ein Terminalsymbol ist und und für Nichtterminale sind. Das Besondere an dieser Form ist also, dass auf der rechten Seite jeder Produktion genau ein Terminalsymbol gefolgt von beliebig vielen Nichtterminalen steht. Es ist aber insbesondere möglich, dass auf der rechten Seite der Produktion nur ein Terminalsymbol steht.

Mit erhält man eine reguläre Grammatik als Spezialfall einer kontextfreien Grammatik in Greibach-Normalform.

Für alle mit gibt es ein , mit , in Greibach-Normalform.

Ist allerdings , dann darf nie auf der rechten Seite einer Produktion vorkommen. Somit ist gewährleistet, dass auch Sprachen, die das leere Wort enthalten, von einer Grammatik in Greibach-Normalform erzeugt werden können.

Konstruktion der GNF[Bearbeiten | Quelltext bearbeiten]

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Der folgende Algorithmus überführt eine Grammatik von der Chomsky-Normalform in die Greibach-Normalform. Hierbei sind im Folgenden:

  • Nichtterminale (hier repräsentiert bereits vorhandene und im Schema neu eingeführte Nichtterminalsymbole)
  • Folgen von Nichtterminalen (z. B. )
  • Terminale und
  • die Menge der Variablen.

Umbenennen von Nichtterminalsymbolen[Bearbeiten | Quelltext bearbeiten]

Für das unten angegebene Schema braucht man eine totale Ordnung auf den Nichtterminalen. Dazu kann man die vorkommenden Nichtterminale in mit umbenennen. Hierzu geht man wie folgt vor:

  • Das erste vorkommende Nichtterminal wird in umbenannt.
  • Das zweite vorkommende Nichtterminal wird in umbenannt.
  • Dieses Schema wird fortgesetzt bis man alle vorkommenden Nichtterminale ersetzt hat.

Beispiel:

  • Die erste vorkommende Variable ist , und wird deswegen in umbenannt.
  • Die zweite vorkommende Variable ist , und wird deswegen in umbenannt.
  • führt man diese Schema weiter kommt man zu

Einsetzen der Produktionen[Bearbeiten | Quelltext bearbeiten]

Gibt es eine Regel der Form mit , muss sie ersetzt werden, indem durch seine Produktionen ersetzt wird.

Beispiel: mit wird zu .

Diese Ersetzung fängt man beim höchsten i an und arbeitet sich bis zur 1 nach unten.

Ersetzen von linksrekursiven Regeln[Bearbeiten | Quelltext bearbeiten]

Linksrekursive Regeln haben die Form , d. h. eine Variable kann wieder auf sich selbst ableiten. Durch den vorherigen Schritt des Algorithmus' ist gesichert, dass entweder mit einem Terminal oder einem beginnen.

Durch wiederholtes Einsetzen sieht man leicht, dass durch linksrekursive Regeln genau der Reguläre Ausdruck

erzeugt werden kann. Dies kann leicht anders erreicht werden:

Man ersetzt die Regeln für linksrekursive durch:

und fügt neue Regeln für ein:

.

Ab jetzt gibt es nur noch Regeln der Form

Ersetzen der Regeln, die mit einem Nichtterminal beginnen[Bearbeiten | Quelltext bearbeiten]

Jetzt kann man in allen Regeln, die zuerst auf ein Nichtterminal ableiten, die Produktionen dieses Nichtterminals einsetzen.

Ab jetzt gibt es nur noch Regeln der Form .

Weiter bis Ende[Bearbeiten | Quelltext bearbeiten]

Nun wird der obige Konstruktionsvorgang statt auf die alten Nichtterminalsymbole analog auf die neu eingeführten Nichtterminalsymbole angewandt.

Eine strengere Variante der Greibach-Normalform[Bearbeiten | Quelltext bearbeiten]

Es ist auch möglich, die Produktionen einer kontextfreien Grammatik so in Greibach-Normalform umzuformen, dass auf jeder rechten Seite maximal 2 Variablen vorkommen. Die resultierenden Produktionen haben dann also die Form , oder .

Konstruktion eines Kellerautomaten aus der GNF[Bearbeiten | Quelltext bearbeiten]

Um aus einer Grammatik in GNF einen Kellerautomaten zu konstruieren, wähle die Zustandsmenge von als , das Kelleralphabet , das Bandalphabet , das Kellerstartsymbol und die Menge der Endzustände . Als Übergangsrelation wähle . akzeptiert über leeren Keller. Beweis per Induktion[1].

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Beweis der Konstruktion des Kellerautomaten aus der GNF