Frage:
Ich muss folgende Grammatik in die Chomsky-Normalform bringen. Wo liegt hier mein Fehler?
Sei G = (Σ, V, S, R) die CH-2-Grammatik mit Σ = {a, b, c, d},
V = {A, B, C, D, S} und der folgenden Regelmenge R:
S → AB | aBCC | C
A → a | BD | ε
B → b
C → c | S
D → d | A | Daa
Mein Lösungsweg
Text erkannt:
1b) 0.Resel: StartsymLol ent fernen
\( S_{0} \longrightarrow A B|a B C C| C \)
\( \overrightarrow{A \rightarrow a} \rightarrow A|B D| \varepsilon \)
\( B \rightarrow b^{b} \mid s \)
1.Resel: \( \varepsilon \) entfernen: \( A \rightarrow \varepsilon \)
\( \begin{array}{l} S_{0} \rightarrow A \\ S \rightarrow A B|B| a B C C \mid C \\ A \rightarrow a \mid B D \\ B \rightarrow b \\ C \rightarrow C \mid S \\ D \rightarrow d|A| D a n \end{array} \)
2.1. Zyklen entternen
\( S_{0} \rightarrow S \)
\( S \rightarrow|+B| B|a B S S| S \Rightarrow S \rightarrow A B|B| a|B S S| C \)
\( A \rightarrow \) a \( 1 B D \)
\( B \rightarrow b \)
\( s \rightarrow c \mid s \)
\( b \rightarrow d|A| \) Dan
Hier noch die zweite Seite:
Text erkannt:
\( 2.2 \) kettenrejel eutternen
\( \begin{array}{l} {[S O]^{+}=\{S\}} \\ {[S]^{+}=\{B\}} \\ {[D]^{+}=\{A\}} \\ S_{0} \rightarrow A B|b| a B S S \mid c \\ S \rightarrow A B|b| a B S S \mid c \\ A \rightarrow a \mid B D \\ B \rightarrow b \end{array} \)
\( D \rightarrow d|a| B D \mid D a n \)
3. Mutuluse Variaberkn, dic nie Terminieren entferne
4. kirvien
\( \begin{array}{l} Y_{n} \rightarrow n \\ S_{0} \rightarrow A B|b| Y_{a} X_{1} \mid C \\ x_{1} \rightarrow B X_{2} \\ x_{2} \rightarrow S S \\ S \rightarrow A|B| b\left|Y_{a} X_{1}\right| c \\ A \rightarrow a \mid B D \\ B \rightarrow b \\ D \rightarrow d|a| B D \mid D X_{3} \\ X_{3} \rightarrow Y_{4} Y_{a} \end{array} \)
Die Lösung wäre die folgende:
S → AB | YaC1 | b | c
A → a | BD | b
B → b
D → d | a | BD | b | DC3 | YaYa
Ya → a
C1 → BC2
C2 → SS
C3 → YaYa
