0 Daumen
396 Aufrufe

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 ?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

\(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.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community