Beweis, dass Sprache nicht regulär ist (Pumping Lemma)

Question

Aufgabe:

$$ \begin{array}{l}{\text { 1. } L_{1}=\{x y | x, y \in\{a, b\} * \text { und } \#_{a}(x)=\#_{b} b(y)\}} \\ {\text { 2. } L_{2}=\left\{x c y | x, y \in\{a, b\}^{*} \text { und } \#_{a}(x)=\#_{b}(y)\right\}}\end{array} $$

Problem/Ansatz:

Bräuchte da ne Hilfestellung, das zu beweisen

Answer 1

L₁ ist regulär.

Angenommen L₂ ist regulär.

Sei n ∈ ℕ, so dass sich jedes Wort w ∈ L₁ mit |w| ≥  n so in w=pqr zerlegen lässt, dass |q| ≥ 1 und |pq| ≤ n und pq^kr ∈ L₂ für jedes k ∈ ℕ ist. (Kurz gesagt, sei n die Pumping-Zahl).

Sei w = aⁿcbⁿ. Dann ist w ∈ L₂.

Für jede Zerlegung w = pqr von w, mit |q| ≥ 1 und |pq| ≤ n ist q = a^m für ein m ∈ ℕ. Laut Pumping Lemma gibt es also ein m ≥ 1, so dass a^n-ma^2mcbⁿ ∈ L₂ ist. Das ist ein Widerspruch zur Definition von L₂.

Zu L₁: Sei w in {a,b}*

Sei w = pq.

Fall 1: #_a(p) = #_b(q). Dann ist w ∈ L₁.

Fall 2: #_a(p) > #_b(q). Entferne den letzten Buchstaben von p und füge ihn an den Anfang von q an.

Fall 2.1: Dieser Buchstabe war ein a. Dann ist #_a(p) um 1 gesunken und #_b(q) ist gleichgeblieben.

Fall 2.2: Dieser Buchstabe war ein b. Dann ist #_a(p) gleich geblieben und #_b(q) um 1 gestiegen.

Fall 3: #_a(p) < #_b(q). Entferne den ersten Buchstaben von q und füge ihn an das Ende von p.

Fall 3.1: Dieser Buchstabe war ein a. Dann ist #_a(p) um 1 gestiegen und #_b(q) ist gleichgeblieben.

Fall 3.2: Dieser Buchstabe war ein b. Dann ist #_a(p) gleichgeblieben und #_b(q) um 1 gesunken.

Wiederhole mit den neuen p und q bis du entweder am Rand des Wortes angekommen bist oder im Fall 1 gelandet bist.

Wie sehen die Wörter aus, bei denen du am Rand des Wortes ankommst?

Wenn du das mal mit w = abaabaaabbaaaabaaaaa und p = abaabaaabb, q = aaaabaaaaa durchspielst, dann wirst du feststellen, dass w ∈ L₁ ist.