Greibach-Normalform

Formale Defninition

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 Regeln (= Produktionen) aus $P$ die Form $A\rightarrow bB_{1}...B_{k}$ mit $k\geq 0$ haben, wobei $A,B_{n}\in N$ (Nichtterminale) und $b\in \Sigma$ (Terminale). 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.

Die Greibach-Normalform hat den Vorteil, dass bei jedem Ableitungsschritt jeweils genau ein Terminalzeichen entsteht.

Konstruktion der GNF

Ausgehend von der Ch-Normalform gibt es folgenden Algorithmus zur Überführung einer Grammatik in die Greibach-Normalform:

Einsetzen der Produktionen

Gibt es eine Regel der Form $A_{i}\rightarrow A_{j}x$ mit $i{>}j$ , muss sie ersetzt werden ( $x$ sei eine beliebige Folge von Nichtterminalen).

Beispiel: $A_{2}\rightarrow A_{1}x$ mit $A_{1}\rightarrow A_{3}{|}A_{4}$ wird zu $A_{2}\rightarrow A_{3}x{|}A_{4}x$ .

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

Ersetzen von Regeln, die zuerst auf sich selbst ableiten

Gibt es eine Regel der Form $A_{i}\rightarrow A_{i}x$ , 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.