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 ε {\displaystyle \varepsilon } -Übergänge.

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

Sei G {\displaystyle G} eine kontextfreie Grammatik (vgl. Chomsky-Hierarchie), also G ∈ Typ 2 {\displaystyle G\in {\mbox{Typ}}_{2}} , mit G = ( N , Σ , P , S ) {\displaystyle G=\left(N,\Sigma ,P,S\right)} . Dabei sei N {\displaystyle N} die Menge der Nichtterminalsymbole, Σ {\displaystyle \Sigma } die Menge der Terminalsymbole, P {\displaystyle P} die Menge von Produktionsregeln und S {\displaystyle S} das Startsymbol. Sei das leere Element ε ∉ L ( G ) {\displaystyle \varepsilon \notin L\left(G\right)} .

G {\displaystyle G} ist in Greibach-Normalform (kurz GNF), wenn alle Produktionen aus P {\displaystyle P} die Form A → b B 1 … B k {\displaystyle A\rightarrow bB_{1}\ldots B_{k}} mit k ≥ 0 {\displaystyle k\geq 0} haben, wobei b {\displaystyle b} ein Terminalsymbol ist und A {\displaystyle A} und B i {\displaystyle B_{i}} für i ∈ { 1 , … , k } {\displaystyle i\in \{1,\ldots ,k\}} 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 k ∈ { 0 , 1 } {\displaystyle k\in \{0,1\}} erhält man eine reguläre Grammatik als Spezialfall einer kontextfreien Grammatik in Greibach-Normalform.

Für alle G ′ ∈ Typ 2 {\displaystyle G'\in {\mbox{Typ}}_{2}} mit ε ∉ L ( G ′ ) {\displaystyle \varepsilon \notin L\left(G'\right)} gibt es ein G ∈ Typ 2 {\displaystyle G\in {\mbox{Typ}}_{2}} , mit L ( G ) = L ( G ′ ) {\displaystyle L\left(G\right)=L\left(G'\right)} , in Greibach-Normalform.

Ist allerdings ( S , ε ) ∈ P {\displaystyle \left(S,\varepsilon \right)\in P} , dann darf S {\displaystyle 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.

Der folgende Algorithmus überführt eine Grammatik G = ( N , Σ , P , S ) {\displaystyle G=\left(N,\Sigma ,P,S\right)} 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]

Hierbei sind im Folgenden:

• A i , B i ∈ N , i ∈ N {\displaystyle A_{i},B_{i}\in N,i\in \mathbb {N} } Nichtterminale (hier repräsentiert A i {\displaystyle A_{i}} bereits vorhandene und B i {\displaystyle B_{i}} im Schema neu eingeführte Nichtterminalsymbole)
• a ∈ Σ {\displaystyle a\in \Sigma } Terminale und
• V = Σ ∪ N {\displaystyle V=\Sigma \cup N} das Vokabular der Grammatik
• x , y ∈ N ∗ {\displaystyle x,y\in N^{*}} Folgen von Nichtterminalen (z. B. x = A 1 A 2 A 3 {\displaystyle x=A_{1}A_{2}A_{3}} )
• α , β ∈ V ∗ {\displaystyle \alpha ,\beta \in V^{*}} Folgen von Terminalen und Nichtterminalen (z. B. x = a A 1 A 2 {\displaystyle x=aA_{1}A_{2}} )

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 A 1 , … , A n {\displaystyle A_{1},\ldots ,A_{n}} mit n = | N | {\displaystyle n=|N|} umbenennen. Hierzu geht man wie folgt vor:

• Das erste vorkommende Nichtterminal wird in A 1 {\displaystyle A_{1}} umbenannt.
• Das zweite vorkommende Nichtterminal wird in A 2 {\displaystyle A_{2}} umbenannt.
• Dieses Schema wird fortgesetzt, bis man alle vorkommenden Nichtterminale ersetzt hat.

Beispiel: P = { S → A D E , A → a D G , G → b } {\displaystyle P=\{S\rightarrow ADE{,}A\rightarrow aDG{,}G\rightarrow b\}}

• Die erste vorkommende Variable ist S {\displaystyle S} , und wird deswegen in A 1 {\displaystyle A_{1}} umbenannt.
• Die zweite vorkommende Variable ist A {\displaystyle A} , und wird deswegen in A 2 {\displaystyle A_{2}} umbenannt.
• führt man diese Schema weiter, kommt man zu P = { A 1 → A 2 A 3 A 4 , A 2 → a A 3 A 5 , A 5 → b } {\displaystyle P=\{A_{1}\rightarrow A_{2}A_{3}A_{4}{,}A_{2}\rightarrow aA_{3}A_{5}{,}A_{5}\rightarrow b\}}

In dieser Phase verwendet der Algorithmus die folgenden zwei Formen von Ersetzungen von Regeln. Nach diesem Schritt gilt für alle Regeln A i → A j x {\displaystyle A_{i}\rightarrow A_{j}\,x} der Grammatik, dass i < j {\displaystyle i<j} .

Mit dieser Ersetzungsregel entfernt der Algorithmus alle Regeln der A i → A j x {\displaystyle A_{i}\rightarrow A_{j}x} . Die Voraussetzung ist, dass es keine rekursiven Regeln für das Nichtterminal A j {\displaystyle A_{j}} gibt. Die Regeln der Form A i → A j x {\displaystyle A_{i}\rightarrow A_{j}x} werden dann ersetzt, indem das Nichtterminal A j {\displaystyle A_{j}} durch seine Produktionen ersetzt werden.

Regel1(
  
    
      
        
          A
          
            i
          
        
        ,
        
          A
          
            j
          
        
      
    
    {\displaystyle A_{i},A_{j}}
  
)
 für alle 
  
    
      
        
          A
          
            i
          
        
        →
        
          A
          
            j
          
        
        
        x
      
    
    {\displaystyle A_{i}\rightarrow A_{j}\,x}
  

    für alle 
  
    
      
        
          A
          
            j
          
        
        →
        β
      
    
    {\displaystyle A_{j}\rightarrow \beta }
  

       Füge 
  
    
      
        
          A
          
            i
          
        
        →
        β
        
        x
      
    
    {\displaystyle A_{i}\rightarrow \beta \,x}
  
 hinzu
    ende
    Entferne 
  
    
      
        
          A
          
            i
          
        
        →
        
          A
          
            j
          
        
        
        x
      
    
    {\displaystyle A_{i}\rightarrow A_{j}\,x}
  

 ende

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

Linksrekursive Regeln haben die Form A i → A i x 1 | A i x 2 | … | A i x n | β 1 | β 2 | … | β n {\displaystyle A_{i}\rightarrow A_{i}\,x_{1}|A_{i}\,x_{2}|\ldots |A_{i}\,x_{n}|\beta _{1}|\beta _{2}|\ldots |\beta _{n}} , 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 A i {\displaystyle A_{i}} durch:

und fügt neue Regeln für B i {\displaystyle B_{i}} ein:

Regel2(
  
    
      
        
          A
          
            i
          
        
      
    
    {\displaystyle A_{i}}
  
)
 für alle 
  
    
      
        
          A
          
            i
          
        
        →
        β
      
    
    {\displaystyle A_{i}\rightarrow \beta }
  

    Füge 
  
    
      
        
          A
          
            i
          
        
        →
        β
        
        
          B
          
            i
          
        
      
    
    {\displaystyle A_{i}\rightarrow \beta \,B_{i}}
  
 hinzu
 ende
 für alle 
  
    
      
        
          A
          
            i
          
        
        →
        
          A
          
            i
          
        
        
        x
      
    
    {\displaystyle A_{i}\rightarrow A_{i}\,x}
  

    Füge 
  
    
      
        
          B
          
            i
          
        
        →
        x
      
    
    {\displaystyle B_{i}\rightarrow x}
  
 hinzu
    Füge 
  
    
      
        
          B
          
            i
          
        
        →
        x
        
        
          B
          
            i
          
        
      
    
    {\displaystyle B_{i}\rightarrow x\,B_{i}}
  
 hinzu
    Entferne 
  
    
      
        
          A
          
            i
          
        
        →
        
          A
          
            i
          
        
        
        x
      
    
    {\displaystyle A_{i}\rightarrow A_{i}\,x}
  

 ende

Der Algorithmus wendet die obigen zwei Ersetzungsregeln für A 1 {\displaystyle A_{1}} bis A m {\displaystyle A_{m}} an, sodass zunächst immer Regeln der Form A i → A j x ,   i > j {\displaystyle A_{i}\rightarrow A_{j}\,x,~i>j} ersetzt werden und dann linksrekursive Regeln mit A i {\displaystyle A_{i}} eliminiert werden.

 für i:=1 bis m
    für j:=1 bis i-1
       Regel1(
  
    
      
        
          A
          
            i
          
        
        ,
        
          A
          
            j
          
        
      
    
    {\displaystyle A_{i},A_{j}}
  
)
    ende
    Regel2(
  
    
      
        
          A
          
            i
          
        
      
    
    {\displaystyle A_{i}}
  
)
 ende

Ab jetzt gibt es nur noch Regeln der Form A i → A j x ,   i < j {\displaystyle A_{i}\rightarrow A_{j}\,x,~i<j} oder der Form A i → x {\displaystyle A_{i}\rightarrow x} . Insbesondere gilt, dass alle A m {\displaystyle A_{m}} Regeln auf der rechten Seite mit einem Terminalsymbol beginnen.

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

 für i:=m-1 bis 1
    für j:=i+1 bis m
         Regel1(
  
    
      
        
          A
          
            i
          
        
        ,
        
          A
          
            j
          
        
      
    
    {\displaystyle A_{i},A_{j}}
  
)
    ende
 ende

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

 für alle 
  
    
      
        
          B
          
            i
          
        
        →
        
          A
          
            j
          
        
        
        x
      
    
    {\displaystyle B_{i}\rightarrow A_{j}\,x}
  

    für alle 
  
    
      
        
          A
          
            j
          
        
        →
        β
      
    
    {\displaystyle A_{j}\rightarrow \beta }
  

       Füge 
  
    
      
        
          B
          
            i
          
        
        →
        β
        
        x
      
    
    {\displaystyle B_{i}\rightarrow \beta \,x}
  
 hinzu
    ende
    Entferne 
  
    
      
        
          B
          
            i
          
        
        →
        
          A
          
            j
          
        
        
        x
      
    
    {\displaystyle B_{i}\rightarrow A_{j}\,x}
  

 ende

Hier wird ausgenutzt, dass die A j {\displaystyle A_{j}} Regeln alle schon in Greibach-Normalform sind und die B i {\displaystyle B_{i}} nie als erstes Symbol der rechten Seite einer Regel auftreten.

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 → a {\displaystyle A_{i}\rightarrow a} , A i → a V {\displaystyle A_{i}\rightarrow aV} oder A i → a V 1 V 2 {\displaystyle A_{i}\rightarrow aV_{1}V_{2}} .

Um aus einer Grammatik G = ( N , T , P , S ) {\displaystyle G=(N,T,P,S)} in GNF einen Kellerautomaten M = ( Z , Σ , Γ , δ , q 0 , Z 0 , F ) {\displaystyle M=(Z,\Sigma ,\Gamma ,\delta ,q_{0},Z_{0},F)} zu konstruieren, wähle die Zustandsmenge von M {\displaystyle M} als Z = { q 0 } {\displaystyle Z=\{q_{0}\}} , das Kelleralphabet Γ = N {\displaystyle \Gamma =N} , das Bandalphabet Σ = T {\displaystyle \Sigma =T} , das Kellerstartsymbol Z 0 = S {\displaystyle Z_{0}=S} und die Menge der Endzustände F = ∅ {\displaystyle F=\emptyset } . Als Übergangsrelation wähle δ ( q 0 , a , A ) = { ( q 0 , x ) : ( A → a x ) ∈ P } {\displaystyle \delta (q_{0},a,A)=\{(q_{0},x):(A\rightarrow ax)\in P\}} . M {\displaystyle M} akzeptiert über leeren Keller. Beweis per Induktion^[2].

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

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 (englisch). 
2. ↑ Beweis der Konstruktion des Kellerautomaten aus der GNF