Schönen guten Abend!
Unser Professor in Theoretischer Informatik hat uns vor Kurzem das
Pumping-Lemma erklärt und natürlich auch bewiesen. Das soll ja anscheinend für alle regulären Sprachen funktionieren. Aber schon in der Vorlesung kam mir folgender Gedanke auf:
Sei die Sprache
§L§ über dem Alphabet
§\Sigma = \{a,b\}§ definiert als
§L=\{aabb\}§. Das müsste ja eine reguläre Sprache sein, weil
- §L\subseteq\Sigma^*§
- sich §L§ durch einen regulären Ausdruck darstellen lässt, nämlich §(aabb)§
- sich §L§ durch einen endlichen Automaten darstellen lässt
- ...
Nun zum Pumping-Lemma:
Für jede reguläre Sprache L gibt es eine natürliche Zahl n, sodass gilt: Jedes Wort z in L mit Mindestlänge n hat eine Zerlegung z=uvw mit den folgenden drei Eigenschaften:
Die beiden Wörter u und v haben zusammen höchstens die Länge n.
Das Wort v ist nicht leer.
Für jede natürliche Zahl (mit 0) i ist das Wort uv^iw in der Sprache L, d. h. die Wörter uw, uvw, uvvw, uvvvw, usw. sind alle in der Sprache L.
Allerdings kann ich kein Wort z=uvw finden, das höchstens die Länge n hat, wobei v nicht das leere Wort ist, sodass ich die Wörter uw, uvw, uvvw, usw. bilden kann (ist ja auch klar, ich habe ja nur ein Wort in der regulären Sprache).
Heißt das jetzt, dass meine Sprache nicht regulär ist oder dass das Pumping-Lemma falsch ist?