imported>Ulanwp: 2 fehlende Sprachparameter eingefügt; 1 Datumsparameter konvertiert

2026-03-12T14:16:49Z

2 fehlende Sprachparameter eingefügt; 1 Datumsparameter konvertiert

Neue Seite

Die '''Greibach-Normalform''' ist ein Begriff der [[Theoretische Informatik|theoretischen Informatik]], der im Zusammenhang mit [[Kontextfreie Sprache|kontextfreien Sprachen]] von Interesse ist. Sie ist nach der [[Vereinigte Staaten|US]]-Informatikerin [[Sheila A. Greibach]] benannt und beschreibt eine [[Kanonische Form|Normalform]] der [[Kontextfreie Grammatik|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 [[Ableitung (Informatik)|Ableitungsschritt]] jeweils genau ein Terminalzeichen entsteht. Damit ist sie der natürliche Zwischenschritt bei der Umformung einer kontextfreien Grammatik in einen äquivalenten nichtdeterministischen [[Kellerautomat]]en 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 Sprache|kontextfreie]] [[Formale Grammatik|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 [[Nichtterminalsymbol]]e, <math>\Sigma</math> die Menge der [[Terminalsymbol]]e, <math>P</math> die Menge von [[Produktionsregel]]n und <math>S</math> das [[Startsymbol]]. Sei das [[Leeres Wort|leere Element]] <math>\varepsilon \notin L \left( G \right)</math>.

<math>G</math> ist in '''Greibach-Normalform''' (kurz '''GNF'''), wenn alle [[Produktionsregel|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 Sprache|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 ==
Der folgende Algorithmus überführt eine Grammatik <math>G = \left( N, \Sigma, P, S \right)</math> von der [[Chomsky-Normalform]] in die Greibach-Normalform.
Der Algorithmus ist von theoretischer Bedeutung, da er zeigt, dass jede kontextfreie Grammatik, nach der nicht das leere Wort abgeleitet werden kann, in eine Greibach-Normalform transformiert werden kann. Die erzeugte Greibach-Normalform ist aber nicht minimal und es existieren Algorithmen mit besserer Laufzeit, die kleine Greibach-Normalformen
berechnen.<ref>{{cite journal |first1=Norbert |last1=Blum |first2=Robert |last2=Koch |date=1999 |title=Greibach Normal Form Transformation Revisited |journal=Information and Computation |volume=150 |issue=1 |pages=112–118 |doi=10.1006/inco.1998.2772 |language=en}}</ref>

=== Notation ===

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>a \in \Sigma</math> Terminale und
* <math>V=\Sigma \cup N</math> das Vokabular der Grammatik
* <math>x, y \in N^*</math> Folgen von Nichtterminalen (z. B. <math>x = A_1 A_2 A_3</math>)
* <math>\alpha, \beta \in V^*</math> Folgen von Terminalen und Nichtterminalen (z. B. <math>x = a A_1 A_2</math>)

=== Vorbereitung ===
Zunächst bringt man die Grammatik in Chomsky-Normalform.
Für das unten angegebene Schema braucht man eine beliebige [[Ordnungsrelation|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>

=== Phase 1 ===
In dieser Phase verwendet der Algorithmus die folgenden zwei Formen von Ersetzungen von Regeln.
Nach diesem Schritt gilt für alle Regeln <math>A_i \rightarrow A_j\,x</math> der Grammatik, dass <math>i < j</math>.

==== Einsetzen der Produktionen ====
Mit dieser Ersetzungsregel entfernt der Algorithmus alle Regeln der <math>A_i \rightarrow A_j x</math>.
Die Voraussetzung ist, dass es keine rekursiven Regeln für das Nichtterminal <math>A_j</math> gibt.
Die Regeln der Form <math>A_i \rightarrow A_j x</math> werden dann ersetzt, indem das Nichtterminal <math>A_j</math> durch seine Produktionen ersetzt werden.

Regel1(<math>A_i, A_j</math>)
'''für''' alle <math>A_i \rightarrow A_j\,x</math>
'''für''' alle <math>A_j \rightarrow \beta</math>
Füge <math>A_i \rightarrow \beta \, x</math> hinzu
'''ende'''
Entferne <math>A_i \rightarrow A_j\,x</math>
'''ende'''

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>.

==== Ersetzen von linksrekursiven Regeln ====
Linksrekursive Regeln haben die Form <math>A_i \rightarrow A_i\, x_1 | A_i\, x_2 | \ldots | A_i\, x_n | \beta_1 | \beta_2 | \ldots | \beta_n</math>, d. h. eine Variable kann wieder auf sich selbst ableiten.
Durch wiederholtes Einsetzen sieht man leicht, dass durch linksrekursive Regeln genau der reguläre Ausdruck

{{Center|<math>(\beta_1 | \beta_2 | \ldots | \beta_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:

{{Center|<math> A_i \rightarrow \beta_1 | \beta_2 | \ldots | \beta_n | \beta_1\, B_i | \beta_2\, B_i | \ldots | \beta_n\, B_i </math>}}

und fügt neue Regeln für <math> B_i </math> ein:

{{Center|<math> B_i \rightarrow x_1 | x_2 | \ldots | x_n | x_1\, B_i | x_2\, B_i | \ldots | x_n\, B_i </math>}}

Regel2(<math>A_i</math>)
'''für''' alle <math>A_i \rightarrow \beta</math>
Füge <math>A_i \rightarrow \beta \, B_i </math> hinzu
'''ende'''
'''für''' alle <math>A_i \rightarrow A_i\,x</math>
Füge <math>B_i \rightarrow x </math> hinzu
Füge <math>B_i \rightarrow x\, B_i </math> hinzu
Entferne <math>A_i \rightarrow A_i\, x</math>
'''ende'''

==== Algorithmus ====
Der Algorithmus wendet die obigen zwei Ersetzungsregeln für <math>A_1</math> bis <math>A_m</math> an,
sodass zunächst immer Regeln der Form <math>A_i \rightarrow A_j\,x, ~i > j </math> ersetzt werden und dann
linksrekursive Regeln mit <math>A_i</math> eliminiert werden.

'''für''' i:=1 bis m
'''für''' j:=1 bis i-1
Regel1(<math>A_i, A_j</math>)
'''ende'''
Regel2(<math>A_i</math>)
'''ende'''

Ab jetzt gibt es nur noch Regeln der Form <math>A_i \rightarrow A_j \, x, ~i < j </math> oder der Form <math>A_i \rightarrow x</math>.
Insbesondere gilt, dass alle <math>A_m</math> Regeln auf der rechten Seite mit einem Terminalsymbol beginnen.

=== Phase 2 ===
In diese Phase werden alle Regeln über die Nichtterminale <math>A_i</math> in die Form <math>A_i \rightarrow a\,N^*</math> transformiert.
Der Algorithmus beginnt bei den <math>A_{m-1}</math> Regeln und ersetzt Regeln, die mit einem Nichtterminal beginnen werden, indem die Produktionen des Nichtterminals eingesetzt werden.
Hier wird ausgenutzt, dass wenn <math>A_{i}</math> Regeln betrachtet werden, die <math>A_{j}</math> Regeln für <math>j > i</math> schon in der gewünschten Form sind.

'''für''' i:=m-1 bis 1
'''für''' j:=i+1 bis m
Regel1(<math>A_i, A_j</math>)
'''ende'''
'''ende'''

=== Phase 3 ===
Im letzten Schritt werden alle Regeln über die neuen Nichtterminale <math>B_i</math> in die Greibach-Normalform transformiert.
Regeln, die mit einem Nichtterminal beginnen, werden ersetzt, indem die Produktionen dieses Nichtterminals eingesetzt werden.

'''für''' alle <math>B_i \rightarrow A_j\,x</math>
'''für''' alle <math>A_j \rightarrow \beta</math>
Füge <math>B_i \rightarrow \beta \, x</math> hinzu
'''ende'''
Entferne <math>B_i \rightarrow A_j\,x</math>
'''ende'''

Hier wird ausgenutzt, dass die <math>A_j</math> Regeln alle schon in Greibach-Normalform sind und die <math>B_i</math> nie als erstes Symbol der rechten Seite einer Regel auftreten.

== 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<ref>[http://www.zaik.uni-koeln.de/AFS/teachings/ws0102/TheoInf/Kapitel10.ps Beweis der Konstruktion des Kellerautomaten aus der GNF]</ref>.

== Literatur ==
* {{Literatur |Autor=[[Uwe Schöning]] |Titel=Theoretische Informatik – kurz gefasst |Auflage=5 |Verlag=Spektrum Akademischer Verlag |Ort=Heidelberg |ISBN=978-3-8274-1824-1 |Kapitel=1.3 Kontextfreie Sprachen}}
* {{Literatur |Autor=[[Ingo Wegener]] |Titel=Theoretische Informatik |TitelErg=Eine algorithmenorientierte Einführung |Verlag=B.G. Teubner |Ort=Stuttgart |ISBN=3-519-02123-4 |Kapitel=7.1 Die Greibach-Normalform für kontextfreie Grammatiken |Sprache=de}}

== Einzelnachweise ==
<references />

[[Kategorie:Automatentheorie]]
[[Kategorie:Compilerbau]]
[[Kategorie:Normalform]]

Greibach-Normalform - Versionsgeschichte

imported>Ulanwp: 2 fehlende Sprachparameter eingefügt; 1 Datumsparameter konvertiert