0 Daumen
265 Aufrufe


Sei \( L_{1}=\left\{b^{2 n} a^{n} \mid n \in \mathbb{N}\right\} \). Betrachten Sie die folgende Sprache über \( \Sigma=\{a, b, c\} \) :
\( L_{2}=\left(\{c\}^{*} L_{1}\right) \cup\{a, b\}^{*} \)
(a) Zeigen Sie, dass mit dem Pumping-Lemma nicht gezeigt werden kann, dass \( L_{2} \) nicht regulär ist.
(b) Sehen Sie sich den Beweis zum Pumping-Lemma genau an und beweisen Sie erweitertes PL.
(c) Zeigen Sie mit dem erweiterten Pumping-Lemma, dass \( L_{2} \) nicht regulär ist.

Avatar von

1 Antwort

0 Daumen

A(L): Die Sprache L ist regulär.

B(L): Es gibt ein n ∈ ℕ, so dass sich jedes Wort x ∈ L mit |x| ≥ n so in x=uvw unterteilen lässt, dass |uv| ≤ n, |v| > 0 und uviw ∈ L für jedes i ∈ ℕ ist.

Das Pumping Lemma besagt A(L) ⇒ B(L).

Dass eine Sprache nicht regulär ist, zeigt man üblicherweise indem man beweist, dass B(L) nicht gilt und folgert dann mittels Kontraposition dass A(L) nicht gilt.

Begründe dass B(L2) gilt.

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