0 Daumen
1,2k Aufrufe

Gegeben sei die Sprache L = { w ∈ {a, b, c}* | |w| = 2^n, n ≥ 0}. Man soll mit dem Pumping-Lemma für reguläre Sprachen zeigen, dass sie nicht regulär ist.


Ich habe mich an ein YouTube Video orientiert. Nun mein Ansatz:
Ich wähle w = aabbcc ∈ L und |w| ist somit 2^2 mit 2 ≥ 0
Den Bedingungen (1 ≤ |v| ≤ |uv| ≤ n), (uv^i o ∈ L) und (uvo = x) folgend, setze ich a = u, abb = v und cc = o. (*)
Ab jetzt bin ich mir nicht mehr sicher: Ich könnte doch einfach i = 0 nehmen und somit hätte ich für uv^i o das wort acc ∉ L und hätte somit bewiesen, dass die Sprache nicht regulär ist? Scheinbar etwas zu einfach oder habe ich bei (*) irgendwelche Regeln missachtet?

Danke im Voraus!

Avatar von

1 Antwort

+1 Daumen
wähle w = aabbcc ∈ L

Aber w ist nicht in L, wegen |w| = 6 ≠ 2n ∀ n ∈ ℕ0.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community