anthropic/claude-opus-4.1

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S→AaX∣XAa∣AaAbS \rightarrow A_aX \mid XA_a \mid A_aA_b
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_bXX
Aa→aA_a \rightarrow a
Ab→bA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S→A∣BC1∣εS \rightarrow A \mid BC_1 \mid \varepsilon
A→SC2∣aA \rightarrow SC_2 \mid a
B→AS∣bB \rightarrow AS \mid b
C1→AAC_1 \rightarrow AA
C2→AC3C_2 \rightarrow AC_3
C3→BBC_3 \rightarrow BB

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S→AB∣DE∣B∣DS \rightarrow AB \mid DE \mid B \mid D
A→AB∣a∣BA \rightarrow AB \mid a \mid B
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BS∣BD \rightarrow BC \mid BS \mid B
E→SS∣CA∣C∣AE \rightarrow SS \mid CA \mid C \mid A

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S→a∣BA∣b∣SC∣AAS \rightarrow a \mid BA \mid b \mid SC \mid AA
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣a∣AAB \rightarrow b \mid SC \mid a \mid AA
C→SS∣b∣SC∣a∣AAC \rightarrow SS \mid b \mid SC \mid a \mid AA

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C
Erreichbar: S,A,B,CS, A, B, C
Nützlich: S,B,CS, B, C
2: mismatch

anthropic/claude-sonnet-4

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S→AaX∣XAa∣AaAbS \rightarrow A_a X \mid X A_a \mid A_a A_b
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_b XX
Aa→aA_a \rightarrow a
Ab→bA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S→A∣BC1∣εS \rightarrow A \mid BC_1 \mid \varepsilon
A→SC2∣aA \rightarrow SC_2 \mid a
B→AS∣bB \rightarrow AS \mid b
C1→AAC_1 \rightarrow AA
C2→AC3C_2 \rightarrow AC_3
C3→BBC_3 \rightarrow BB

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S→AB∣DE∣BS \rightarrow AB \mid DE \mid B
A→AB∣a∣BA \rightarrow AB \mid a \mid B
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BS∣BD \rightarrow BC \mid BS \mid B
E→SS∣CA∣A∣CE \rightarrow SS \mid CA \mid A \mid C
removed: {('S', ('D',))}

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S→a∣BA∣b∣SC∣AAS \rightarrow a \mid BA \mid b \mid SC \mid AA
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣a∣AAB \rightarrow b \mid SC \mid a \mid AA
C→SS∣b∣SC∣a∣AAC \rightarrow SS \mid b \mid SC \mid a \mid AA

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C
Erreichbar: S,A,B,CS, A, B, C
Nützlich: S,B,CS, B, C
2: mismatch

deepseek/deepseek-chat-v3.1

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S→AaX∣XAa∣AaAbS \rightarrow A_a X \mid X A_a \mid A_a A_b  
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_b X X  
Aa→aA_a \rightarrow a  
Ab→bA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S → A | B C | ε  
C → A A  
A → S D | a  
D → A E  
E → B B  
B → A S | b

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S → AB | DE | B | D  
A → AB | a | B  
B → b | BB | D  
C → A | c  
D → BC | BS | B  
E → SS | CA | C | A

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S → a | BA | b | SC | AA  
A → a | AA  
B → b | SC | a | AA  
C → SS | b | SC | a | AA

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C  
Erreichbar: S,A,B,CS, A, B, C  
Nützlich: S,B,CS, B, C
2: mismatch

deepseek/deepseek-r1-0528

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S→AaX∣XAa∣AaAbS \rightarrow A_a X \mid X A_a \mid A_a A_b
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_b X X
Aa→aA_a \rightarrow a
Ab→bA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S→A∣BC1∣εS \rightarrow A \mid B C_1 \mid \varepsilon
A→SC2∣aA \rightarrow S C_2 \mid a
B→AS∣bB \rightarrow A S \mid b
C1→AAC_1 \rightarrow A A
C2→AC3C_2 \rightarrow A C_3
C3→BBC_3 \rightarrow B B

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S→AB∣DE∣B∣DS \rightarrow AB \mid DE \mid B \mid D
A→AB∣a∣BA \rightarrow AB \mid a \mid B
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BS∣BD \rightarrow BC \mid BS \mid B
E→SS∣CA∣C∣AE \rightarrow SS \mid CA \mid C \mid A

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S→a∣b∣BA∣SC∣AAS \rightarrow a \mid b \mid BA \mid SC \mid AA
A→a∣AAA \rightarrow a \mid AA
B→a∣b∣SC∣AAB \rightarrow a \mid b \mid SC \mid AA
C→a∣b∣AA∣SC∣SSC \rightarrow a \mid b \mid AA \mid SC \mid SS

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C
Erreichbar: S,A,B,CS, A, B, C
Nützlich: S,B,CS, B, C
2: mismatch

google/gemini-2.5-pro

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S→AaX∣XAa∣AaAbS \rightarrow A_aX \mid XA_a \mid A_aA_b
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_bXX
Aa→aA_a \rightarrow a
Ab→bA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S→A∣BC1∣εS \rightarrow A \mid BC_1 \mid \varepsilon
A→SC2∣aA \rightarrow SC_2 \mid a
B→AS∣bB \rightarrow AS \mid b
C1→AAC_1 \rightarrow AA
C2→AC3C_2 \rightarrow AC_3
C3→BBC_3 \rightarrow BB

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S→AB∣DE∣B∣DS \rightarrow AB \mid DE \mid B \mid D
A→AB∣a∣BA \rightarrow AB \mid a \mid B
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BS∣BD \rightarrow BC \mid BS \mid B
E→SS∣CA∣A∣CE \rightarrow SS \mid CA \mid A \mid C

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S→a∣b∣AA∣BA∣SCS \rightarrow a \mid b \mid AA \mid BA \mid SC
A→a∣AAA \rightarrow a \mid AA
B→a∣b∣AA∣SCB \rightarrow a \mid b \mid AA \mid SC
C→a∣b∣AA∣SC∣SSC \rightarrow a \mid b \mid AA \mid SC \mid SS

Subproblem e (3.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S, B, C
Erreichbar: S, A, B, C
Nützlich: S, C

openai/gpt-5

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S -> A_a X | X A_a | A_a A_b
X -> SS | S | ε | A_b X X
A_a -> a
A_b -> b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S -> A | B C1 | ε
C1 -> A A
A -> S C2 | a
C2 -> A C3
C3 -> B B
B -> A S | b

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S -> AB | DE | B | D
A -> AB | a | B
B -> b | BB | D
C -> A | c
D -> BC | BS | B
E -> SS | CA | C | A

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S -> a | BA | b | SC | AA
A -> a | AA
B -> b | SC | a | AA
C -> SS | b | SC | a | AA

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C
Erreichbar: S,A,B,CS, A, B, C
Nützlich: S,B,CS, B, C
2: mismatch

openai/gpt-oss-120b

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S→AaX∣XAa∣AaAbS \rightarrow A_aX \mid XA_a \mid A_aA_b
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_bXX
Aa→aA_a \rightarrow a
Ab→bA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S  →  A  ∣  B X1  ∣  εS \;\rightarrow\; A \;\mid\; B\,X_1 \;\mid\; \varepsilon
X1  →  A AX_1 \;\rightarrow\; A\,A
A  →  S C2  ∣  aA \;\rightarrow\; S\,C_2 \;\mid\; a
C2  →  A C3C_2 \;\rightarrow\; A\,C_3
C3  →  B BC_3 \;\rightarrow\; B\,B
B  →  A S  ∣  bB \;\rightarrow\; A\,S \;\mid\; b

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S→AB∣DE∣B∣DS \rightarrow AB \mid DE \mid B \mid D
A→AB∣a∣BA \rightarrow AB \mid a \mid B
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c 
D→BC∣BS∣BD \rightarrow BC \mid BS \mid B 
E→SS∣CA∣A∣CE \rightarrow SS \mid CA \mid A \mid C

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S  →  a∣BA∣b∣SC∣AAS \;\rightarrow\; a \mid BA \mid b \mid SC \mid AA 
A  →  a∣AAA \;\rightarrow\; a \mid AA 
B  →  b∣SC∣a∣AAB \;\rightarrow\; b \mid SC \mid a \mid AA 
C  →  SS∣b∣SC∣a∣AAC \;\rightarrow\; SS \mid b \mid SC \mid a \mid AA

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C  
Erreichbar: S,A,B,CS, A, B, C  
Nützlich: S,B,CS, B, C
2: mismatch

qwen/qwen3-235b-a22b

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S → A_a X | X A_a | A_a A_b  
X → SS | S | ε | A_b X X  
A_a → a  
A_b → b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S → A | B F | ε  
F → A A  
A → a | S C  
C → A E  
E → B B  
B → A S | b

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S → AB | B | DE | D  
A → AB | B | a  
B → BB | D | b  
C → A | c  
D → BC | B | BS  
E → SS | CA | A | C

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S → a | BA | b | SC | AA  
A → a | AA  
B → b | a | SC | AA  
C → SS | b | a | SC | AA

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C  
Erreichbar: S,A,B,CS, A, B, C  
Nützlich: S,B,CS, B, C
2: mismatch

qwen/qwen3-235b-a22b-thinking-2507

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S→AaX∣XAa∣AaAbS \rightarrow A_aX \mid XA_a \mid A_aA_b
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_bXX
Aa→aA_a \rightarrow a
Ab→bA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S→A∣BC∣εS \rightarrow A \mid BC \mid \varepsilon
A→SD∣aA \rightarrow SD \mid a
B→AS∣bB \rightarrow AS \mid b
C→AAC \rightarrow AA
D→AED \rightarrow AE
E→BBE \rightarrow BB

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S→AB∣DE∣B∣DS \rightarrow AB \mid DE \mid B \mid D
A→AB∣B∣aA \rightarrow AB \mid B \mid a
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣B∣BSD \rightarrow BC \mid B \mid BS
E→SS∣CA∣C∣AE \rightarrow SS \mid CA \mid C \mid A

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S→a∣b∣BA∣SC∣AAS \rightarrow a \mid b \mid BA \mid SC \mid AA
A→a∣AAA \rightarrow a \mid AA
B→a∣b∣SC∣AAB \rightarrow a \mid b \mid SC \mid AA
C→SS∣a∣b∣SC∣AAC \rightarrow SS \mid a \mid b \mid SC \mid AA

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C
Erreichbar: S,A,B,CS, A, B, C
Nützlich: S,B,CS, B, C
2: mismatch

x-ai/grok-4

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (X→α)∈P(X\rightarrow\alpha)\in P, mit X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen A→ϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G′)=L(G)∖{ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{B→ϵB \rightarrow \epsilon} und \alert{A→αBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{A→αβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G′)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{A→BA \rightarrow B} und \alert{B→αB \rightarrow \alpha} in P^\hat{P} mit α≠A\alpha \neq A, so füge auch \alert{A→αA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis G′G' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes a∈Σa\in\Sigma, das in einer rechten Seite der Länge ≥2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge ≥2\geq 2 durch AaA_a, und füge Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S→AaX∣XAa∣AaAbS \rightarrow A_a X \mid X A_a \mid A_a A_b
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_b X X
Aa→aA_a \rightarrow a
Ab→bA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S→A∣BC∣εS \rightarrow A \mid B C \mid \varepsilon
A→SD∣aA \rightarrow S D \mid a
B→AS∣bB \rightarrow A S \mid b
C→AAC \rightarrow A A
D→AED \rightarrow A E
E→BBE \rightarrow B B

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S→AB∣DE∣B∣DS \rightarrow AB \mid DE \mid B \mid D
A→AB∣a∣BA \rightarrow AB \mid a \mid B
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BS∣BD \rightarrow BC \mid BS \mid B
E→SS∣CA∣C∣AE \rightarrow SS \mid CA \mid C \mid A

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S→a∣b∣AA∣BA∣SCS \rightarrow a \mid b \mid AA \mid BA \mid SC
A→a∣AAA \rightarrow a \mid AA
B→a∣b∣AA∣SCB \rightarrow a \mid b \mid AA \mid SC
C→a∣b∣AA∣SC∣SSC \rightarrow a \mid b \mid AA \mid SC \mid SS

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C
Erreichbar: S,A,B,CS, A, B, C
Nützlich: S,B,CS, B, C
2: mismatch