Pumping-Lemma - Verständnisfrage zu einem konkreten Beispiel

[Jack159]

Hallo,

ich habe eine Frage zum Pumping-Lemma bezüglich regulärer Sprachen um bei einer Sprache zu zeigen, dass diese nicht regulär ist.

Es geht um folgendes Beispiel:
http://de.wikipedia.org/wiki/Pumping-Lemma#Beispiel

Ich verstehe folgenden Schritt nicht:
...gemäß Bedingung 1 (Das Wort v ist nicht leer) besteht uv und somit auch v ausschließlich aus a's...

Ich verstehe nicht, wieso uv und somit auch v ausschließlich aus a's bestehen sollen oder müssen?

Beispiel:

w=aaabbb

Dies zerlege ich nun wie folgt:

u = a
v = aab
w = bb

Diese Aufteilung wäre laut dem Pumping-Lemma ja erlaubt und in dem Falle besteht mein uv = aaab nicht ausschließlich aus a's. Wie kommen die da also darauf, dass uv und auch v ausschließlich aus a's bestehen?

 

[Ochse]

Mhh, verstehe dein Problem nicht ganz. Gemäß Bedingung 1 ist uv kleiner gleich n. In deinem Beispiel gilt jetzt aber |u|=1, |v|=3 und |uv|=n+1=4. Also ist deine Zerlegung schonmal nicht korrekt, da die Gesamtlänge |w|=2n=6 ist.

 

[NuminousDestiny]

Mein Vorredner hat recht, deine Zerlegung ist nicht korrekt, da |uv| gemäß Bed.1 = j-1 und somit stets <= n ist.

Du hast eine Sprache deren erste n Zeichen aus a's besteht -> uv = a^j-1.
Sprich uv hat nur j-1 a's von den n a's .

In deiner Zerlegung wäre n = 3, sodass du das Wort aaabbb erhalten würdest.

uv dürfen aber höchstens aaa belegen da |aaa| <= n wäre
Deine Zerlegung verletzt die 1. Bedingung

 

[Jack159]

Habe es mir eben nochmal angeschaut und es ist mir sofort klar gworden. Danke euch