Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Kontextfreie Sprachen (CFG) » Nutzlose Variablen
Ableitungsbaum Kontextfreie Sprachen (CFG) Chomsky Normalform (CNF)
Unterabschnitte

Nutzlose Variablen

Definition

Nutzlose Variablen sind solche Variablen, von denen kein Wort abgeleitet werden kann. Sie tragen nicht zur Erzeugung der Sprache bei.

Algorithmus

Die Entfernung von nutzlosen Variablen erfolgt, indem wir alle Non-Terminale markieren, die nicht nutzlos sind, also aus denen wir ein Wort machen können:
  1. Durch Inspektion aller Regeln ermitteln wir die Menge

    \begin{displaymath}N=\{A\in V:A\rightarrow w\, f\uml {u}r\,ein\,w\in\Sigma^{*}\}\end{displaymath}

    (Also alle Nonterminale der Regeln $A\rightarrow a$ nehmen wir sofort auf.)
  2. Gibt es eine Regel

    \begin{displaymath}B\rightarrow x_{1}A_{1}x_{2}A_{2}\ldots x_{n}A_{n}\end{displaymath}

    in G, wobei

    \begin{displaymath}alle\,A_{i}\in N\end{displaymath}

    füge $B$ in $N$ ein. Wiederhole Schritt 2 solange, bis keine Regel mehr diese Eigenschaft hat, daß alle Nontermials auf der rechten Seite Element in $N$ sind und das Nonterminal auf der linken Seite noch nicht.
  3. Die Menge $V\backslash N$ ist die Menge der nutzlosen Variablen.

Ableitungsbaum Kontextfreie Sprachen (CFG) Chomsky Normalform (CNF)