0 Daumen
580 Aufrufe

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.

Avatar von

1 Antwort

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

Dann ist uvw ∉ L.

Eine mögliche Zerlegung von x ist u = bb, v=an-2, w = aaban.

Dann ist uvw ∈ L, aber uv2w ∉ 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.

Avatar von 105 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community