Pumping-Lemma für EA-Sprachen

Question

Guten Tag,

kann es sein, dass auf Folie 2-25 im zweiten Kapitel der Vorlesung ein Fehler in der Definition des Pumping-Lemmas vorliegt?

Bei Punkt (1) steht dort, dass Betrag(xy) kleiner gleich n ist. Müsste es aber nicht heißen, dass Betrag(xz) kleiner gleich n ist?

Falls es sich nicht um einen Fehler handelt, so würde ich mich über eine kurze Erklärung freuen, wieso dies so ist.

Viele Grüße

Answer 1

Hello,

es ist kein Fehler. Um y zu bekommen, das sich beliebig pumpen lässt, reicht es aus nur bis die ersten n Zeichen von w zu betrachten. Schauen Sie bitte auch die Folie 26 an.

Pradyumn Shukla

Comments

Danke für die schnelle Antwort! Ich verstehe allerdings auch mit Folie 26 nicht ganz, wieso dort k kleiner gleich n sein muss. Dass dann Betrag(xy) kleiner gleich n ist, macht Sinn, aber wieso ist k kleiner gleich n?
Mich verwirrt z.B., dass dann dieser Automat ja nicht dem Lemma entsprechen würde:
- Automat mit drei Zuständen
- solange ich a eingebe, bleibe ich in s0
- wenn ich b eingebe, springe ich in s1 und bleibe dort, solange b eingegeben wird
- wenn ich c eingebe, springe ich in s2 und bleibe dort, solange c eingegeben wird
- c ist Endzustand
Wenn ich jetzt z.B. das Wort w = abbbbbbc (Betrag von w = 8) eingebe, dann wird dieses ja eigentlich vom Automaten akzeptiert und ich brauche nur die drei Zustände (n = 3) des endlichen Automaten. Aber Betrag von (xy) wäre in diesem Fall = 7 und damit größer als n, oder nicht?
Ich hoffe, dieses Beispiel ist nachvollziehbar. Was ist an diesem Beispiel falsch?
Viele Grüße

---

Die Schleife kann aber schon nach drei Schritten auftreten. Genauer: Muss (laut PPL) auftreten können. Lesen Sie sich das Kapitel im Lehrbuch durch!

Answer 2

Haben Sie sich dieses Kapitel mal im Lehrbuch durchgelesen? Beim Pumping-Lemma, das vielen Studierenden anfangs Probleme bereitet, haben wir besonders darauf geachtet, eine schlüssige und einfache Beschreibung zu formulieren. Ich bin mir sicher, dass Sie es nach der Lektüre verstehen werden.

Comments

Danke erneut für diese super-schnelle Antwort. Ich glaube, ich habe meinen Verständnisfehler gefunden. Bei y handelt es sich nur um den ersten Durchlauf der Schleife, jeder weitere Durchlauf zählt nicht zu y, sondern es ergibt sich yy, yyy, yyyy usw.
Ist das korrekt?
Tatsächlich ist das im Lehrbuch klarer formuliert, danke für den Hinweis. Leider haben wir Studenten nicht die Zeit, jedes Thema auch im Lehrbuch durchzuarbeiten, da wir dafür einfach zu viele Fächer gleichzeitig belegen müssen. An dieser Stelle war es aber auf jeden Fall hilfreich :D
Viele Grüße und schönen Abend :)

---

Ja, genau, mindestens der erste. Es können auch mehrere sein, denn ein EA mit vielen Zuständen kann trotzdem sehr schnell eine Schleife produzieren - muss er aber nicht. Spätestens nach $n$ Übergängen kommt aber auf jeden Fall eine.