Kettenregeln

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

Eine Regel (l$\to$r) mit | r| = 1 heißt Kettenregel.

Der Ketten-Abschluß von G ist die kleinste Menge R' mit

• R $\subseteq$ R'
• falls (A$\to$B) $\in$ R und (B$\to$r) $\in$ R', dann (A$\to$r) $\in$ R'.

Aufgaben: Wieviele Regeln kann man maximal hinzufügen?

Satz: Zu jeder CFG G existiert eine CFG G' ohne Kettenregeln mit L(G) = L(G').

Beweis: G' = ($\Sigma$, V, S, R' ohne Kettenregeln).

Aufgabe: falls R epsilon-frei, dann auch R'.