Kreise und kreisfreie Grammatiken

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

Def: eine Kreis-Ableitung ist von der Form A$\to_{R}^{+}$A für eine Variable A.

Satz: für jede CFG G gibt es eine kreisfreie CFG G' mit L(G) = L(G').

Idee: G epsilon-frei: G₁, kettenfrei: G₂, ist kreisfrei.

Aufgaben:

• Anwenden auf S$\to$$\epsilon$ | SS | aSb
• Behauptung beweisen, dabei beachten:
• wie wird $\epsilon$ $\in$ L(G) behandelt?
• Wie kann man entscheiden, ob gegebenes G kreisfrei ist (ohne alle Ableitungen aufzuzählen)?