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.
Pumping Lemma
Ich habe ein bisschen Probleme damit, beim Pumping Lemma richtig zu argumentieren.
Konkret habe ich mir Aufgabe 5 der Probeklausur angeschaut.
Da habe ich brav das negierte Lemma abgeschrieben, also was zu zeigen ist.
Beim Zeigen komm ich dann aber nicht recht weiter. Man soll ja argumentieren, dass das
w für alle Zerlegungen und bei entsprechendem Pumpen nicht mehr in L ist.
Das hab ich jetzt mehr oder weniger nochmal als Fließtext formuliert, also dass ein Auslassen
oder Wiederholen von Zeichen dazu führt, dass das erhaltene Wort nicht mehr in L ist.
Letzten Endes ist das aber auch nichts anderes als die Aussage des Zeichensalats am Anfang…
Soll man evtl einen Induktionsbeweis über die Struktur der Sprache führen?
Also ich würde mich über etwas Inspiration freuen;-) Oder über eine Bestätigung, dass eine
Wiedergabe des Lemmas in eigenen Worten reicht.
Ich weiss nicht, ob das deine Frage beantwortet, aber ich fange grundsätzlich an mit “Sei p ∈ N beliebig aber fest” und gebe dann (in Abhängigkeit von p) ein x ∈ L an mit |x|≥p. (Spoiler: In dieser Aufgabe konkret kann man z.B. x als ein Wort festlegen, das mit p-mal Klammerauf beginnt.) Dann hat man noch u,v,w ∈ ∑* beliebig aber fest mit den Bedingungen x=uvw, v≠ε, |uv|≤p, aus denen man (wenn man p schlau gewählt hat) direkt folgern kann dass gewisse Dinge für v gelten und uv*w nicht Teilmenge von L ist.
Mal als Beispiel für L=a[sup]n[/sup]b[sup]n[/sup], das Schema ist eigentlich meistens gleich:
Sei l>=1. Wähle z=a[sup]l[/sup]b[sup]l[/sup].
Es gilt für alle Zerlegungen z = uvw mit |v|>=1 und |uv|<=l:
u=a[sup]m[/sup], v=a[sup]p[/sup], w=asup[/sup]b[sup]l[/sup] mit 0<=m<=l-p und 1<=p<=l.
=> uv[sup]0[/sup]w = uw = a[sup]m[/sup]asup[/sup]b[sup]l[/sup] = a[sup]l-p[/sup]b[sup]l[/sup] ist nicht in L.
=> L nicht regulär
1 „Gefällt mir“
Vielen Dank, hat mir beides sehr geholfen!