Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Kellerautomaten Aufwärts: Kontextfreie Sprachen (CFG) Vorherige Seite: Abschlußeigenschaften   Inhalt

Unterabschnitte

Griebach Normalform

Satz

Sei $G$ eine CFG. G ist eine Griebach Normalform, falls eine Produktionen in $G$ von der Form

\begin{displaymath}A\rightarrow aB_{1}B_{2}\ldots B_{k}\end{displaymath}

wobei $k=0$ sein kann und auch $a=\epsilon$ möglich ist.

Konstruktionsalgorithmus

  1. Wenn bei der Regel $A_{i}\rightarrow A_{j}x$ das $i$ größer als das $j$ ist, wird $A_{i}$ überbrückt.
    $A_{2}\rightarrow A_{1}x$ $A_{1}\rightarrow A_{3}\vert A_{4}$ wird zu $A_{2}\rightarrow A_{3}x\vert A_{4}x$.
  2. Wenn die Regel der Form $A_{i}\rightarrow A_{i}x$ ist, wird diese entfernt und stattdessen $B_{i}\rightarrow xB_{i}$ und $B_{i}\rightarrow x$ eingefügt.
    Es werden für alle Regeln $A_{i}\rightarrow y$ (wobei $y=a\in\Sigma$ oder $aA_{j}$...) $A_{i}\rightarrow yB_{i}$ eingefügt, damit die Kette nicht zerstört wird.
    Am Ende findet man dann keine linksrekursiven Regeln mehr. Alle Terminale sind nach links gerutscht.
  3. Eliminierung der Regeln, in denen ein Terminal nicht an erster Stelle steht:
    Beginn mit den größten $i$-Werten:
    Für alle Regeln $A_{i}\rightarrow A_{j}x$ füge für alle Regeln $A_{j}\rightarrow\beta$ eine Regel $A_{i}\rightarrow \beta x$ ein und entferne die Originalregel $A_{i}\rightarrow A_{j}x$. Am Ende wird kein $\beta$ mehr vorne steht.
  4. Tue dasselbe wie für die A-Regeln für die B-Regeln.