Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Grammatiken » Transformation um die ε-Freiheit bis auf S → ε in Typ 1 herzustellen
Grafische Darstellung der Chomskyhierarchie Grammatiken Abschlußeigenschaften von Sprachtypen
Unterabschnitte

Transformation um die ε-Freiheit bis auf S → ε in Typ 1 herzustellen

Es gibt eine kleine technische Panne bei

\begin{displaymath}Typ\, 2\subset Typ\, 1\end{displaymath}


\begin{displaymath}kontextfrei\subset kontextsensitiv\end{displaymath}

Bei Typ 2 darf auf der rechten Seite in jeder beliebigen Regel das $\epsilon$ stehen. Bei Typ 1 jedoch nicht. Wir können jedoch jede kontextsensitive Grammatik in der die Regel $\vert u\vert\leq\vert v\vert$ durch das $\epsilon$ verletzt ist, in eine äquivalente regelkonforme Grammatik umformen.

Algorithmus

Markierungsalgorithmus:
  • Markiere alle Non-Terminale $A$ mit $A\rightarrow\epsilon$
  • Solange es Regeln gibt, so daß die rechte Seite aus lauter markierten Non-Terminalen besteht, markiere das Non-Terminal auf der linken Seite.
  • Gebe alle markierten Non-Terminale als $V_{\epsilon}$ aus.
Transformationsalgorithmus:
  • Falls das Nonterminal $S$ in irgendeiner Regel auf der rechten Seite vorkommt, füge $S'\rightarrow s$ ein.
  • Führe den oben beschriebenen Markierungsalgorithmus durch.
  • Entferne alle Regeln $A\rightarrow\epsilon$ aus der Grammatik
  • Wenn $S'\in v_{\epsilon}$ füge $S'\rightarrow\epsilon$ ein.
  • Solange es eine Regel $B\rightarrow xAy$ mit $\vert x\vert+\vert y\vert\geq 1$ und $A\in V_{\epsilon}$ gibt, füge $B\rightarrow xy$ ein, wenn diese Regel noch nicht existiert.

Beispiel

Transformation von folgender Grammatik $G$ in eine äquivalente $\epsilon$-freie CFG:
$S$ $\rightarrow$ $aCb\vert ACB$
$A$ $\rightarrow$ $aAA\vert DDDD\vert aab$
$B$ $\rightarrow$ $AAC\vert b$
$C$ $\rightarrow$ $SB\vert\epsilon$
$D$ $\rightarrow$ $AacbS\vert CE$
$E$ $\rightarrow$ $C\vert bca$
Markiert werden nacheinander folgende Nichtterminale (letztendlich alle):

\begin{displaymath}C,E,D,A,B,S\end{displaymath}

Wir streichen die Regel

\begin{displaymath}C\rightarrow\epsilon\end{displaymath}

$S$ ist Element von $V_{\epsilon}$. Wir müssen ein Startsymbol $S'$ hinzufügen:

\begin{displaymath}S'\rightarrow s\end{displaymath}

Folgende Regeln entstehen nun bei dem Durchlauf des Transformationsalgorithmusses:
$S'$ $\rightarrow$ $S$
$S$ $\rightarrow$ $aCb\vert ACB\vert ab\vert AB\vert CB\vert B\vert AC\vert A\vert C$
$A$ $\rightarrow$ $aAA\vert DDDD\vert aab\vert DDD\vert DD\vert D\vert aA\vert a$
$B$ $\rightarrow$ $AAC\vert b\vert AA\vert AC\vert C\vert A$
$C$ $\rightarrow$ $SB\vert S\vert B$
$D$ $\rightarrow$ $AacbS\vert CE\vert E\vert C\vert acbS\vert Aacb\vert acb$
$E$ $\rightarrow$ $C\vert bca$
Grafische Darstellung der Chomskyhierarchie Grammatiken Abschlußeigenschaften von Sprachtypen