0 Daumen
106 Aufrufe

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

von

1 Antwort

+1 Daumen
 
Beste Antwort

L1 ist regulär.

Angenommen L2 ist regulär.

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

Sei w = ancbn. Dann ist w ∈ L2.

Für jede Zerlegung w = pqr von w, mit |q| ≥ 1 und |pq| ≤ n ist q = am für ein m ∈ ℕ. Laut Pumping Lemma gibt es also ein m ≥ 1, so dass an-ma2mcbn ∈ L2 ist. Das ist ein Widerspruch zur Definition von L2.

Zu L1: Sei w in {a,b}*

Sei w = pq.

Fall 1: #a(p) = #b(q). Dann ist w ∈ L1.

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 ∈ L1 ist.

von 1,9 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community