Greibach-Normalform

Normalform für kontextfreie Grammatiken

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.

Formale Definition

Bearbeiten

Sei   eine kontextfreie Grammatik (vgl. Chomsky-Hierarchie), also  , mit  . Dabei sei   die Menge der Nichtterminalsymbole,   die Menge der Terminalsymbole,   die Menge von Produktionsregeln und   das Startsymbol. Sei das leere Element  .

  ist in Greibach-Normalform (kurz GNF), wenn alle Produktionen aus   die Form   mit   haben, wobei   ein Terminalsymbol ist und   und   für   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   erhält man eine reguläre Grammatik als Spezialfall einer kontextfreien Grammatik in Greibach-Normalform.

Für alle   mit   gibt es ein  , mit  , in Greibach-Normalform.

Ist allerdings  , dann darf   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

Bearbeiten

Der folgende Algorithmus überführt eine Grammatik   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.[1]

Notation

Bearbeiten

Hierbei sind im Folgenden:

  •   Nichtterminale (hier repräsentiert   bereits vorhandene und   im Schema neu eingeführte Nichtterminalsymbole)
  •   Terminale und
  •   das Vokabular der Grammatik
  •   Folgen von Nichtterminalen (z. B.  )
  •   Folgen von Terminalen und Nichtterminalen (z. B.  )

Vorbereitung

Bearbeiten

Zunächst bringt man die Grammatik in Chomsky-Normalform. Für das unten angegebene Schema braucht man eine beliebige totale Ordnung auf den Nichtterminalen. Dazu kann man die vorkommenden Nichtterminale in   mit   umbenennen. Hierzu geht man wie folgt vor:

  • Das erste vorkommende Nichtterminal wird in   umbenannt.
  • Das zweite vorkommende Nichtterminal wird in   umbenannt.
  • Dieses Schema wird fortgesetzt, bis man alle vorkommenden Nichtterminale ersetzt hat.

Beispiel:  

  • Die erste vorkommende Variable ist  , und wird deswegen in   umbenannt.
  • Die zweite vorkommende Variable ist  , und wird deswegen in   umbenannt.
  • führt man diese Schema weiter, kommt man zu  

In dieser Phase verwendet der Algorithmus die folgenden zwei Formen von Ersetzungen von Regeln. Nach diesem Schritt gilt für alle Regeln   der Grammatik, dass  .

Einsetzen der Produktionen

Bearbeiten

Mit dieser Ersetzungsregel entfernt der Algorithmus alle Regeln der  . Die Voraussetzung ist, dass es keine rekursiven Regeln für das Nichtterminal   gibt. Die Regeln der Form   werden dann ersetzt, indem das Nichtterminal   durch seine Produktionen ersetzt werden.

Regel1( )
 für alle  
    für alle  
       Füge   hinzu
    ende
    Entferne  
 ende

Beispiel:   mit   wird zu  .

Ersetzen von linksrekursiven Regeln

Bearbeiten

Linksrekursive Regeln haben die Form  , 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

 

erzeugt werden kann. Dies kann leicht anders erreicht werden:

Man ersetzt die Regeln für linksrekursive   durch:

 

und fügt neue Regeln für   ein:

 
Regel2( )
 für alle  
    Füge   hinzu
 ende
 für alle  
    Füge   hinzu
    Füge   hinzu
    Entferne  
 ende

Algorithmus

Bearbeiten

Der Algorithmus wendet die obigen zwei Ersetzungsregeln für   bis   an, sodass zunächst immer Regeln der Form   ersetzt werden und dann linksrekursive Regeln mit   eliminiert werden.

 für i:=1 bis m
    für j:=1 bis i-1
       Regel1( )
    ende
    Regel2( )
 ende

Ab jetzt gibt es nur noch Regeln der Form   oder der Form  . Insbesondere gilt, dass alle   Regeln auf der rechten Seite mit einem Terminalsymbol beginnen.

In diese Phase werden alle Regeln über die Nichtterminale   in die Form   transformiert. Der Algorithmus beginnt bei den   Regeln und ersetzt Regeln, die mit einem Nichtterminal beginnen werden, indem die Produktionen des Nichtterminals eingesetzt werden. Hier wird ausgenutzt, dass wenn   Regeln betrachtet werden, die   Regeln für   schon in der gewünschten Form sind.

 für i:=m-1 bis 1
    für j:=i+1 bis m
         Regel1( )
    ende
 ende

Im letzten Schritt werden alle Regeln über die neuen Nichtterminale   in die Greibach-Normalform transformiert. Regeln, die mit einem Nichtterminal beginnen, werden ersetzt, indem die Produktionen dieses Nichtterminals eingesetzt werden.

 für alle  
    für alle  
       Füge   hinzu
    ende
    Entferne  
 ende

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

Eine strengere Variante der Greibach-Normalform

Bearbeiten

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

Konstruktion eines Kellerautomaten aus der GNF

Bearbeiten

Um aus einer Grammatik   in GNF einen Kellerautomaten   zu konstruieren, wähle die Zustandsmenge von   als  , das Kelleralphabet  , das Bandalphabet  , das Kellerstartsymbol   und die Menge der Endzustände  . Als Übergangsrelation wähle  .   akzeptiert über leeren Keller. Beweis per Induktion[2].

Literatur

Bearbeiten
  • Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1, 1.3 Kontextfreie Sprachen.
  • Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4, 7.1 Die Greibach-Normalform für kontextfreie Grammatiken.

Einzelnachweise

Bearbeiten
  1. Norbert Blum, Robert Koch: Greibach Normal Form Transformation Revisited. In: Information and Computation. 150. Jahrgang, Nr. 1, 1999, S. 112–118, doi:10.1006/inco.1998.2772.
  2. Beweis der Konstruktion des Kellerautomaten aus der GNF