welche der drei Sprachen sie kontextfreie und welche nicht?

Question

1. \( L_{1}=\left\{a^{i} b^{j} c^{i} d^{j} \mid i, j \in \mathbf{N}\right\} \)
2. \( L_{2}=\left\{a^{2^{n}} \mid n \geq 0\right\} \),
3. \( L_{3}=\left\{w_{1} \ldots w_{2 m} \mid m \geq 0 ; w_{i} \in\{a, b, c\}, w_{2 m+1-i} \in\{a, b, c\} \backslash\left\{w_{i}\right\}\right. \) für alle \( \left.i \in\{1, \ldots, m\}\right\} \),

welche der drei Sprachen sie kontextfreie und welche nicht ?

Answer 1

\(L_1\) und \(L_2\) sind nicht kontextfrei. Das lässt sich mit dem Pumping-Lemma zeigen. \(L_3\) ist kontextfrei. Man kann eine kontextfreie Grammatik angeben.