Greibach-Normalform


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

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

Inhaltsverzeichnis

Formale Definition

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, Σ 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 Bi für i\in\{1,\ldots,k\} Nichtterminale sind. 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

Ausgehend von der Chomsky-Normalform gibt es folgenden Algorithmus zur Überführung einer Grammatik in die Greibach-Normalform. Hierbei sind A_i, B_i \in N, i \in \mathbb{N} Nichtterminale, x, y \in N^\star Folgen von Nichtterminalen, a \in \Sigma Terminale und V=\Sigma \cup N die Menge der Variablen.

Einsetzen der Produktionen

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

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 Ai 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 Bi 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

Entfernen der Regeln, die mit einem Nichtterminal beginnen

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

Nun werden die Konstruktionsregeln auf alle Regeln von B analog 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 A_i\rightarrow a, A_i\rightarrow aV oder A_i\rightarrow aV_1V_2.

Konstruktion eines Kellerautomaten aus der GNF

Um aus einer Grammatik G = (N,T,P,S) in GNF einen Kellerautomaten M = (Z,Σ,Γ,δ,q0,Z0,F) zu konstruieren, wähle die Zustandsmenge von M als Z = {q0}, das Kelleralphabet Γ = N, das Bandalphabet Σ = T, das Kellerstartsymbol Z0 = 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

Einzelnachweise

  1. Beweis der Konstruktion des Kellerautomaten aus der GNF

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Greibach — Sheila A. Greibach (* 1939 in New York City) ist eine Mathematikerin und arbeitet hauptsächlich in der theoretischen Informatik. Nach ihr ist die Greibach Normalform benannt. Im Jahr 1960 erwarb sie ihren A.B. degree vom Radcliffe College (das… …   Deutsch Wikipedia

  • Normalform — Unter einer Normalform (auch kanonische Form) versteht man eine Darstellung mit bestimmten vorgegebenen Eigenschaften. Mitunter ist die Darstellung eindeutig. Formal ist eine Normalform ein letztes Element in einer Kette von einer wohlfundierten… …   Deutsch Wikipedia

  • Sheila Greibach — Sheila A. Greibach (* 1939 in New York City) ist eine Mathematikerin und arbeitet hauptsächlich in der theoretischen Informatik. Nach ihr ist die Greibach Normalform benannt. Im Jahr 1960 erwarb sie ihren A.B. degree vom Radcliffe College (das… …   Deutsch Wikipedia

  • Sheila A. Greibach — Sheila Adele Greibach (* 6. Oktober 1939 in New York City) ist eine Mathematikerin und arbeitet hauptsächlich in der theoretischen Informatik. Nach ihr ist die Greibach Normalform benannt. Im Jahr 1960 erwarb sie ihren A.B. degree vom Radcliffe… …   Deutsch Wikipedia

  • Greibachnormalform — 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 …   Deutsch Wikipedia

  • Kontextfreie Grammatiken — Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ 2 Grammatiken der Chomsky Hierarchie. Inhaltsverzeichnis 1 Definition 2 Normalformen 3 Von G erzeugte Sprache 4 Eigenschaften …   Deutsch Wikipedia

  • Typ2-Grammatik — Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ 2 Grammatiken der Chomsky Hierarchie. Inhaltsverzeichnis 1 Definition 2 Normalformen 3 Von G erzeugte Sprache 4 Eigenschaften …   Deutsch Wikipedia

  • Kanonische Form — Unter einer Normalform versteht man eine Darstellung, die bestimmte vorgegebene Eigenschaften hat. Insbesondere bezeichnet Normalform in der Mathematik eine Darstellung eines Objektes, die bestimmte vorgegebene Eigenschaften hat und für alle… …   Deutsch Wikipedia

  • Kontextfreie Grammatik — In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik eine Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminal auf eine beliebig lange Folge von Nichtterminalen und Terminale abgeleitet wird …   Deutsch Wikipedia

  • GN-F — GNF steht für: Global Nature Fund, eine Umwelt und Naturstiftung mit Sitz in Radolfzell am Bodensee Greibach Normalform, ein Begriff der theoretischen Informatik Groupement National de Football, die marokkanische Fußballmeisterschaft Guinea Franc …   Deutsch Wikipedia