L regulär =>
Es ex. eine nat. Zahl N (z.B. Zustandszahl)
So daß für alle Worte w aus L mit
|w|>=N
Eine Zerlegung w=uvx
ex. mit |uv|<=N (Anfangsstück) und |v|>=1 (Pumpstelle)
So daß für alle i>=0 gilt: uvix ist aus L.
Die Kontraposition dieses Satzes dient zum Nachweis der Nichtregularität:
Für alle Nat. Zahlen N
Gibt es ein Wort w aus L mit |w|>=N
So daß für
alle Zerlegungen w=uvx mit |uv|<=N und |v|>=1
Ein i>=0 ex., so daß gilt: uvix ist nicht aus L.
=> L ist nicht regulär.
WICHTIG:
Der umgekehrte Schluß (<=) gilt nicht!
D.h., Regularität ist nicht durch das Pumping-Lemma beweisbar!
Beispiel:
L={wwumgedreht| w Wort aus Sigma*}
Sei N nat.Zahl
Wähle w=0N1N1N0N,
|w|=4N>=N
Sei w=uvx beliebige Zerlegung
mit |uv|<=N, |v|>=1
Wähle i=2: Dann folgt weil uv nur aus 0en bestehen kann: w'=uvvx=0N+|v|1N1N0N.
Wegen |v|>=1 kann w' nicht aus L sein.