Zeigen Sie mithilfe des Pumping-Lemmas das die Sprache L = {bb(a^n)b(a^n) | n = 1} nicht regulär ist.

Question

Aufgabe:

Zeigen Sie mithilfe des Pumping-Lemmas das die Sprache L = {bb(a^n)b(a^n) | n >= 1} nicht regulär ist.

Problem/Ansatz:

Ich bin leider mit Beweisführungen unsicher. Wäre sehr dankbar wenn mir jemand bestätigen könnte ob der Beweis so richtig wäre ? Vielen Dank im voraus.

Angenommen L ist regulär und sei n die Zahl aus Pumping-Lemma. Offensichtlich ist x = bb(a^n)b(a^n) ∈ L

und |x| >= n. Dann können wir x zerlegen in x = uvw mit |uv| <= n und |v| > 0.

Eine mögliche Zerlegung wäre: u = bb, v = a^(n-2) , w = b(a^n). Bemerkung: v = a^(n-2) soass |uv| <= n stets gilt.

Für diese Zerlegung wählen wir i = 0, dann gilt:

u(v^i)w = uw = bbb(a^n) ∉L, da nach den ersten zwei b's kein a auftaucht.

Answer 1

Eine mögliche Zerlegung wäre: u = bb, v = a^(n-2) , w = b(aⁿ-1)

Dann ist uvw ∉ L.

Eine mögliche Zerlegung von x ist u = bb, v=a^n-2, w = aabaⁿ.

Dann ist uvw ∈ L, aber uv²w ∉ L. Leider reicht das nicht, um zu zeigen dass L nicht regulär ist. Dazu musst du nämlich zeigen, dass keine geeignete Zerlegung existiert, dass also alle Zerlegungen ungeeignet sind.

Comments

Danke erstmal für deine Antwort.

Wie zeige ich das denn das keine Zerlegung geeigent ist ?

Muss ich alle Zerlegungen durchgehen?

Also u = leer, v = bb(a^(n-2)), w = aab(a^n) und

u = b, v = b(a^(n-2)), w = aab(a^n) usw ?

---

Muss ich alle Zerlegungen durchgehen? 

Ja.