Beweisen oder widerlegen Sie:
(a) Es gibt Grammatiken, die zwar nicht rechtslinear sind, die aber äquivalent zu einer rechtslinearen Grammatik sind, d.h. die erzeugten Sprachen sind gleich.
(b) Das Komplement von \( L=\left\{b^{n} a^{4 n} \mid n \in \mathbb{N}\right\} \) über \( \Sigma=\{a, b\} \) ist kontextfrei aber nicht regulär.
(c) Das Komplement von \( \left\{b^{n} a^{2 n} c^{n} \mid n \in \mathbb{N}\right\} \) über \( \Sigma=\{a, b, c\} \) ist nicht kontextfrei.
(d) Seien \( L_{1} \subseteq L_{2} \) und \( L_{2} \subseteq L_{3} \) Sprachen.
1. Ist \( L_{1} \) nicht regulär, so ist auch \( L_{3} \) nicht regulär.
2. Ist \( L_{3} \) nicht kontextfrei, so ist auch \( L_{2} \) nicht kontextfrei.
(Hinweis: Als Gegenbeispiele dienen oft Sprachen über dem Alphabet \( \{a\} \), insbesondere \( L_{\text {prim }}=\left\{a^{p} \mid p\right. \) Primzahl \( \left.\}.\right) \)
