Aufgabe:
Betrachten Sie die Grammatik \( G=(\Sigma, N, S, P) \) mit \( \Sigma=\{a, b, c\}, N=\{S, B, C, X\} \) und
\( \begin{aligned} P=\{S& \rightarrow a S a \mid a X a \\ X & \rightarrow B C X \mid B C \\ C B & \rightarrow B C \\ C a & \rightarrow c a \\ C c & \rightarrow c c \\ B c & \rightarrow b c \\ B b &\rightarrow b b\} \end{aligned} \)
(a) Geben Sie eine Ableitung des Wortes \( w=a b b c c a \) bezüglich der Grammatik \( G \) an, wobei Sie nur die unmittelbare Ableitungsrelation nutzen.
(b) Modifizieren Sie \( G \) zu \( G^{\prime} \), so dass \( \lambda \in L\left(G^{\prime}\right) \) und \( L\left(G^{\prime}\right)=L(G) \cup\{\lambda\} \) gelten, indem Sie das Verfahren aus der Vorlesung in dem Abschnitt, ,Sonderregelung für das leere Wort " anwenden.
(c) Geben Sie \( L(G) \) formal als Menge von Wörtern an, ohne weiteren Bezug auf \( G \) zu nehmen.
(d) Betrachten Sie die Grammatik \( G^{\prime \prime}=\left(\Sigma, N, S, P^{\prime \prime}\right) \) mit
\( \Sigma=\{a, b, c\} \quad \text { und } \quad N=\{S, A, B, C, X\} \)
und
\( \begin{aligned} P^{\prime \prime}=\{S& \rightarrow a S a \mid a X a \\ X & \rightarrow B C, \\ B & \rightarrow b B \mid b, \\ & \rightarrow c C \mid c A, \\ A &\rightarrow a,\} \end{aligned} \)
Sind die beiden Grammatiken \( G \) und \( G^{\prime \prime} \) äquivalent? Begründen Sie Ihre Antwort.
