Erreichbare und produktive Variablen

Id: reduziert.tex,v 1.1 2004/12/14 12:36:40 waldmann Exp

Für eine CFG G heißt die Variable A

• erreichbar, falls $\exists$u, v $\in$ ($\Sigma$ $\cup$ V)^* : S$\to_{R}^{*}$uAv
• produktiv, falls $\exists$w $\in$ $\Sigma^{*}_{}$ : A$\to_{R}^{*}$w

Aufgabe: wie kann man entscheiden, ob diese Eigenschaften zutreffen (ohne alle Ableitungen aufzuzählen)?

Vergleiche mit gleichen Begriffen für Zustände von endlichen Automaten.