Zeigen Sie, dass mit dem Pumping-Lemma nicht gezeigt werden kann, dass L_{2} nicht regulär ist.

Question

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.

Answer 1

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 uvⁱw ∈ 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(L₂) gilt.