Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Palindrome - Pumping Lemma
Hi alle!
Ich müsste mal wissen, ob folgender Beweis korrekt ist:
Es sei L die Spache der Palindrome über {0,1}*.
Mit dem Pumping Lemma betrachte ich folgendes Wort x: u v w
w bestehe aus: v^R u^R. Damit meine ich: u v v-reverse u-reverse. Dieses Wort müsste dann Element von L sein - da es ein Palindrom ist. Die Folgenden Eigenschaften sollen gelten:
|x| >= p; |uv| <= p; |v| >= 1;
Ist L regulär, so müsste jedes Wort der Form u v^i w Element von L sein für alle i Element der Natürlichen Zahlen.
Betrachte ich allerdings das Wort u v^3 w, also u v^3 v^R u^R, ist dieses nicht mehr Element von L. Damit ist L irregulär.
Ist das so in Ordnung?
Christian
re
Ich hätte den Beweis etwas formaler geführt:
Sei W=a[sup]n[/sup]ba[sup]n[/sup], |W|=2n+1.
Dann gilt für jede beliebige Zerlegung von W: v=a+, da gelten muss: |uv|≤n und |v|≥1.
Wenn du v jetzt hochpumpst, dann erhältst du ein Wort der Form a[sup]m[/sup]ba[sup]n[/sup], und das ist kein Palindrom mehr und damit W auch nicht in L enthalten.
Edit: n sei die Pumpzahl 
Ja, man muss auf jeden Fall das entsprechende Wort angeben, wie z.B. Sleipnirs a^n b a^n (bzw. auf die Aufgabe bezogen 0^n 1 0^n 
)
Nur als Hinweis, die Lösungen für die Blätter 9-12 sind äquivalent zu denen des WS0506, ist mir nur gerade aufgefallen, da die Lösungen 9-12 fehlten.