Greibach-Normalform

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

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

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, also eine Teilmenge der kontextfreien Grammatiken, die gegenüber der Menge der allgemeinen kontextfreien Grammatiken nichts an Ausdrucksstärke einbüßt. 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

1 Formale Definition
2 Konstruktion der GNF
3 Eine strengere Variante der Greibach-Normalform

[Bearbeiten] Formale Definition

Sei $G$ eine kontextfreie Grammatik (vgl. Chomsky-Hierarchie), also $G \in \mbox{Typ}_2$ . Sei das leere Element $\epsilon \notin L \left( G \right)$ .

$G$ , mit $G = \left( N, \Sigma, P, S \right)$ , 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. Mit $k = 1$ ist also eine reguläre Grammatik ein Spezialfall einer kontextfreien Grammatik in Greibach-Normalform.

Für alle $G' \in \mbox{Typ}_2$ mit $\epsilon \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.

[Bearbeiten] 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.

[Bearbeiten] 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 oben.

S–>AA|0 A–>SS|1

[Bearbeiten] Ersetzen von Regeln, die zuerst auf sich selbst ableiten

Gibt es eine Regel der Form $A_i \rightarrow A_ix$ , so entferne diese Produktion von $A i$ und füge $B_i \rightarrow xB_i | x$ sowie für alle anderen $A_i \rightarrow y$ eine Regel $A_i \rightarrow yB_i$ hinzu.

Ab jetzt gibt es nur noch Regeln der Form $A_i \rightarrow aV^* {|} V^*$ . Dies sagt aber nichts aus, denn $V *$ könnte mit $A i$ beginnen und der Rest ist auch Halbwissen.

[Bearbeiten] 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^*$ .

[Bearbeiten] Weiter bis Ende

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

[Bearbeiten] Eine strengere Variante der Greibach-Normalform

Es ist auch möglich, die Produktionen einer kontextfreien Grammatik so in Greibach-Normalform umzuformen, dass auf den rechten Seiten 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$ .