Normalformen von CFG

Erreichbare und produktive Variablen

$$Id: reduziert.tex,v 1.2 2003/12/03 11:51:10 joe Exp $$

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

• erreichbar, falls $\exists u,v\in (\Sigma\cup V)^* : S \to_R^* u A v$
• 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.

Reduzierte Grammatiken

Def: Die Grammatik $G$ heißt reduziert,

wenn alle Variablen erreichbar und produktiv sind.

Satz: zu jeder CFG $G$ gibt es eine reduzierte CGF $G'$ mit $L(G)=L(G')$.

Beweis: lösche in $G$ zuerst alle nicht produktiven Variablen,

dann alle (im Rest) nicht erreichbaren Variablen

(jeweils mit allen Regeln, in denen sie vorkommen)

Aufgabe: warum gerade diese Reihenfolge?

Nullierbare Variablen

$$Id: null.tex,v 1.2 2003/12/03 11:51:10 joe Exp $$

Def: Eine Variable $A$ heißt nullierbar, falls $A \to_R^* \epsilon$.

Die Menge der nullierbaren Variablen von $G$

ist die kleinste Menge $N \subseteq V$ mit:

• wenn $(A \to \epsilon) \in R$, dann $A \in N$
• wenn $(A \to x) \in R$ und $x \in N^*$, dann $A \in N$

Bemerkung: der erste Fall ist tatsächlich im zweiten enthalten.

Def: eine Regel $A \to r$ heißt nullierbar, falls $r\to_R^* \epsilon$.

Epsilon-freie Grammatiken

$$Id: epsfree.tex,v 1.2 2003/12/03 11:51:10 joe Exp $$

Def: eine CFG $G$ heißt epsilon-frei, falls $\forall (A \to r)\in R: r \neq \epsilon$.

Bemerkung: wenn $G$ epsilon-frei, dann $\epsilon \notin L(G)$.

Satz: Für jede CFG $G$ existiert eine epsilon-freie CGF $G'$ mit $L(G') = L(G) \setminus \{\epsilon\}$.

Beweis: Wende auf alle rechten Regelseiten die Substitution

$A \to$ ( wenn $A$ nullierbar, dann $\{A, \epsilon\}$, sonst $\{A\}$)

an, und lösche dann alle Epsilon-Regeln.

Aufgabe: Konstruiere $G'$ für $G$ mit $R = \{ S \to \epsilon \mid aSb \mid SS \}$.

Kettenregeln

$$Id: kette.tex,v 1.2 2003/12/03 11:51:10 joe Exp $$

Eine Regel $(l \to r)$ mit $\vert r\vert=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'$.

Kreise und kreisfreie Grammatiken

$$Id: kreis.tex,v 1.1 2003/12/03 11:51:10 joe 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_1$, kettenfrei: $G_2$, ist kreisfrei.

Aufgaben:

• Anwenden auf $S \to \epsilon \mid SS \mid 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)?