Greibach-Normalform - LinkFang.de





Greibach-Normalform


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 [math]\varepsilon[/math]-Übergänge.

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

Formale Definition

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

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

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

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

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung.

Der folgende Algorithmus überführt eine Grammatik [math]G = \left( N, \Sigma, P, S \right)[/math] von der Chomsky-Normalform in die Greibach-Normalform. Hierbei sind im Folgenden:

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

Umbenennen von Nichtterminalsymbolen

Für das unten angegebene Schema braucht man eine totale Ordnung auf den Nichtterminalen. Dazu kann man die vorkommenden Nichtterminale in [math]A_1, \ldots, A_n[/math] mit [math]n = |N|[/math] umbenennen. Hierzu geht man wie folgt vor:

  • Das erste vorkommende Nichtterminal wird in [math]A_1[/math] umbenannt.
  • Das zweite vorkommende Nichtterminal wird in [math]A_2[/math] umbenannt.
  • Dieses Schema wird fortgesetzt bis man alle vorkommenden Nichtterminale ersetzt hat.

Beispiel: [math]P = \{S \rightarrow ADE {, } A \rightarrow aDG {, } G \rightarrow b \}[/math]

  • Die erste vorkommende Variable ist [math]S[/math], und wird deswegen in [math]A_1[/math] umbenannt.
  • Die zweite vorkommende Variable ist [math]A[/math], und wird deswegen in [math]A_2[/math] umbenannt.
  • führt man diese Schema weiter kommt man zu [math]P = \{A_1 \rightarrow A_2 A_3 A_4 {, } A_2 \rightarrow a A_3 A_5 {, } A_5 \rightarrow b \}[/math]

Einsetzen der Produktionen

Gibt es eine Regel der Form [math]A_i \rightarrow A_jx[/math] mit [math]i {\gt} j[/math], muss sie ersetzt werden, indem [math]A_j[/math] durch seine Produktionen ersetzt wird.

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

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

Ersetzen von linksrekursiven Regeln

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

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

[math](y_1 | y_2 | \ldots | y_n)(x_1 | x_2 | \ldots | x_n) ^* [/math]

erzeugt werden kann. Dies kann leicht anders erreicht werden:

Man ersetzt die Regeln für linksrekursive [math] A_i [/math] durch:

[math] A_i \rightarrow y_1 | y_2 | \ldots | y_n | y_1B_i | y_2B_i | \ldots | y_nB_i [/math]

und fügt neue Regeln für [math] B_i [/math] ein:

[math] B_i \rightarrow x_1 | x_2 | \ldots | x_n | x_1B_i | x_2B_i | \ldots | x_nB_i [/math].

Ab jetzt gibt es nur noch Regeln der Form [math]A_i \rightarrow A_jx_1 | A_jx_2 | \ldots | A_jx_n , ~i \lt j [/math]

Ersetzen der Regeln, die mit einem Nichtterminal beginnen

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 [math]A_i \rightarrow aV^*[/math].

Weiter bis Ende

Nun wird der obige Konstruktionsvorgang statt auf die alten Nichtterminalsymbole [math]A_i[/math] analog auf die neu eingeführten Nichtterminalsymbole [math]B_i[/math] angewandt.

Eine strengere Variante der Greibach-Normalform

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 [math]A_i\rightarrow a[/math], [math]A_i\rightarrow aV[/math] oder [math]A_i\rightarrow aV_1V_2[/math].

Konstruktion eines Kellerautomaten aus der GNF

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

Literatur

Einzelnachweise

  1. Beweis der Konstruktion des Kellerautomaten aus der GNF

Kategorien: Compilerbau | Theorie formaler Sprachen | Automatentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Greibach-Normalform (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.