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 \varepsilon-Übergänge.

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

Formale Definition[Bearbeiten]

Sei G eine kontextfreie Grammatik (vgl. Chomsky-Hierarchie), also G \in \mbox{Typ}_2, mit G = \left( N, \Sigma, P, S \right). Dabei sei N die Menge der Nichtterminalsymbole, \Sigma die Menge der Terminalsymbole, P die Menge von Produktionsregeln und S das Startsymbol. Sei das leere Element \varepsilon \notin L \left( G \right).

G ist in Greibach-Normalform (kurz GNF), wenn alle Produktionen aus P die Form A \rightarrow bB_1\ldots B_k mit k \ge 0 haben, wobei b ein Terminalsymbol ist und A und B_i für i\in\{1,\ldots,k\} 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 k \in \{0,1\} erhält man eine reguläre Grammatik als Spezialfall einer kontextfreien Grammatik in Greibach-Normalform.

Für alle G' \in \mbox{Typ}_2 mit \varepsilon \notin L \left( G' \right) gibt es ein G \in \mbox{Typ}_2, mit L \left( G \right) = L \left( G' \right), in Greibach-Normalform.

Ist allerdings \left( S, \varepsilon \right) \in P, dann darf S 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]

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.

Ausgehend von der Chomsky-Normalform gibt es folgenden Algorithmus zur Überführung einer Grammatik G = \left( N, \Sigma, P, S \right) in die Greibach-Normalform. Hierbei sind im Folgenden:

  • A_i, B_i \in N, i \in \mathbb{N} Nichtterminale (hier repräsentiert A_i bereits vorhandene und B_i im Schema neu eingeführte Nichtterminalsymbole)
  • x, y \in N^* Folgen von Nichtterminalen (z.B. x = A_1 A_2 A_3)
  • a \in \Sigma Terminale und
  • V=\Sigma \cup N die Menge der Variablen.

Umbenennen von Nichtterminalsymbolen[Bearbeiten]

Gegebenenfalls kann man vorkommende Nichtterminale in A_1, \ldots, A_n mit n = |N| umbenennen um das unten angegebene Schema korrekt nachvollziehen zu können.
Hierzu geht man wie folgt vor:

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

Beispiel: P = \{S \rightarrow ADE {, } A \rightarrow aDG {, } G \rightarrow b \}

  • Erste vorkommende Variable S wird in A_1 umbenannt.
  • Zweite vorkommende Variable A wird in A_2 umbenannt.
  • führt man diese Schema weiter kommt man zu P = \{A_1 \rightarrow A_2 A_3 A_4 {, } A_2 \rightarrow a A_3 A_5 {, } A_5 \rightarrow b \}

Einsetzen der Produktionen[Bearbeiten]

Gibt es eine Regel der Form A_i \rightarrow A_jx mit i {>} j, muss sie ersetzt werden.

Beispiel: A_2 \rightarrow A_1x mit A_1 \rightarrow A_3 {|} A_4 wird zu A_2 \rightarrow A_3x {|}A_4x.

Diese Ersetzung fangen wir beim höchsten i an und arbeiten uns bis zur 1 nach unten.

Ersetzen von linksrekursiven Regeln[Bearbeiten]

Linksrekursive Regeln haben die Form A_i \rightarrow A_ix_1 | A_ix_2 | \ldots | A_ix_n | y_1 | y_2 | \ldots  | y_n, d.h eine Variable kann wieder auf sich selbst ableiten. Durch den vorherigen Schritt des Algorithmus' ist gesichert, dass y_1, \ldots, y_n entweder mit einem Terminal oder einem A_j,~ i < j beginnen.

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

(y_1 | y_2 | \ldots  | y_n)(x_1 | x_2 | \ldots | x_n) ^*

erzeugt werden kann. Dieser kann leicht simuliert werden:
Ersetze die Regeln für  A_i mit:

 A_i \rightarrow y_1 | y_2 | \ldots  | y_n | y_1B_i | y_2B_i | \ldots  | y_nB_i

und füge neue Regeln für  B_i ein:

 B_i \rightarrow x_1 | x_2 | \ldots | x_n | x_1B_i | x_2B_i | \ldots | x_nB_i .

Ab jetzt gibt es nur noch Regeln der Form A_i \rightarrow A_jx_1 | A_jx_2 | \ldots | A_jx_n , ~i < j

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

Jetzt können wir in allen Regeln, die zuerst auf ein Nichtterminal ableiten, die Produktionen dieses Nichtterminals einsetzen.

Ab jetzt gibt es nur noch Regeln der Form A_i \rightarrow aV^*.

Weiter bis Ende[Bearbeiten]

Nun werden die Konstruktionsregeln auf alle Regeln von B analog angewandt.

Eine strengere Variante der Greibach-Normalform[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 A_i\rightarrow a, A_i\rightarrow aV oder A_i\rightarrow aV_1V_2.

Konstruktion eines Kellerautomaten aus der GNF[Bearbeiten]

Um aus einer Grammatik G = (N, T, P, S) in GNF einen Kellerautomaten M=(Z,\Sigma,\Gamma,\delta,q_0,Z_0,F) zu konstruieren, wähle die Zustandsmenge von M als Z=\{ q_0 \}, das Kelleralphabet \Gamma = N, das Bandalphabet \Sigma = T, das Kellerstartsymbol Z_0 = S und die Menge der Endzustände F = \emptyset. Als Übergangsrelation wähle \delta (q_0,a,A) = \{(q_0,x):(A \rightarrow ax) \in P\}. M akzeptiert über leeren Keller. Beweis per Induktion[1].

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Beweis der Konstruktion des Kellerautomaten aus der GNF