Was ist los mit meinem Pumping Lemma Beweis?

8

Die Sprache ist offensichtlich regulär - zum Beispiel entspricht sie dem regulären Ausdruck . Das folgende Argument des Pumping Lemma scheint jedoch zu zeigen, dass es nicht regelmäßig ist. Was ist falsch gelaufen?L={02n | n0}(00)

Ich habe einen Weg gefunden, einen Eingang als , der die Anforderungen des Pump-Lemmas erfüllt, aber es ist nicht wahr, dass für alle  . Bedeutet das nicht, dass die Sprache nicht regelmäßig ist?sxyzxyizLi

Genauer gesagt , sagt der Pumping - Lemma für reguläre Sprachen , dass, wenn eine Sprache  regulär ist, gibt Pumplänge existiert , so dass eine beliebige Zeichenfolge mit kann geschrieben werden solche Das:Lp1sL|s|>ps=xyz

  1. |y|1
  2. |xy|p
  3. xyizL für alle .i0

Nehmen wir also und schreiben es als (dh , , ). Dies erfüllt 1. und 2. Wenn wir jedoch , erhalten wir , was nicht in ist  weil seine Länge ungerade ist. Es sieht also so aus, als ob die Sprache doch nicht regelmäßig ist.s=02ps=ϵ002p1x=ϵy=0z=02p1i=0xyiz=ϵ0002p1=02p1L


Dies ist als Referenzfrage gedacht, die einen häufigen Fehler bei der Verwendung des Pump-Lemmas für reguläre Sprachen veranschaulicht. Vielen Dank an Ariel für das Erkennen des Problems in der Originalversion der Frage.

Blitzbrand
quelle
4
Das Pump-Lemma besagt, dass für Wörter, die größer als eine Länge sind, eine solche Zerlegung existiert. Sie haben eine bestimmte Zerlegung gezeigt, die nicht funktioniert, aber ein Wort mit einer Länge von mehr als 2 und . (Gott erbarme dich meiner Seele für die Antwort)py=02
Ariel
Es gibt ziemlich gute Anleitungen in früheren Beiträgen, z. B. cs.stackexchange.com/questions/1031/…
Ran G.
2
@RanG. Dieser Beitrag ist eine hervorragende Anleitung, um zu beweisen, dass eine Sprache nicht regelmäßig ist, aber wir scheinen häufig Fragen zu bekommen, bei denen jemand versucht hat, das Pump-Lemma anzuwenden und genau diesen Fehler gemacht hat. Ich denke, es ist hilfreicher, darauf hinzuweisen, was der Fehler in einem solchen Beweis ist (z. B. indem Sie diese Frage als Betrogener markieren), als zu sagen: "Hier erfahren Sie, wie Sie es richtig machen. Sie finden heraus, was der Unterschied zwischen Ihrem ist." Ansatz und der richtige ist. "
David Richerby
2
@ DavidRicherby Sie haben Recht, bei dieser Frage geht es nicht darum, Unregelmäßigkeiten beim Pumpen zu zeigen. Der häufigste Missbrauch des Lemmas ist das Missverständnis der Quantifizierer, und der Leitfaden zu der von mir erwähnten Frage versucht, dieses Problem zu lösen (z. B. durch Schreiben in Fettdruck: alle Möglichkeiten, es zu partitionieren usw.)
Ran G.
Das Lemma stellt sicher, dass es eine Aufteilung gibt, die funktioniert, wenn die Sprache regelmäßig ist. Um zu beweisen, dass es nicht regelmäßig ist, müssen Sie beweisen, dass keine Aufteilung funktioniert.
vonbrand

Antworten:

6

Das Problem liegt in den Quantifizierern. Das Pump-Lemma besagt, dass jeder String mit als geschrieben werden kann , so dass die drei Eigenschaften gelten. Es heißt nicht, dass jede Art, es als schreiben , die die ersten beiden Eigenschaften hält, auch die dritte hält.s|s|p xyzxyz

Für die Sprache gehen wir wie folgt vor. Beachten Sie zunächst, dass wir , da wir bei gezwungen sind, , , und Sie haben dies bereits in der Frage gezeigt das funktioniert nicht Mit können wir also schreiben als ( , , ). Wir haben , und für alle{02nn0}p2p=1x=ϵy=0z=02p1p2s=02ps=ϵ0002(p1)x=ϵy=00z=02(p1)|ϵ00|p|00|>1(00)i02(p1)Li0. Daher gibt es eine Möglichkeit, die Zeichenfolge als zerlegen , die alle Eigenschaften erfüllt, obwohl die erste Zerlegung, an die Sie gedacht haben, nicht funktioniert hat.xyz

Um zu zeigen, dass eine Sprache nicht regulär ist, müssen Sie zeigen, dass jede Zerlegung in , die die ersten beiden Eigenschaften erfüllt, die dritte nicht erfüllt. Es reicht nicht aus, nur zu zeigen, dass eine Zerlegung nicht funktioniert.xyz

Um zu verstehen, warum das Pump-Lemma so ist, wie es ist, hilft es, über den Beweis nachzudenken. Wenn eine Sprache regulär ist, wird sie von einigen EDA akzeptiert. Dieser DFA hat eine Reihe von Zuständen: Nennen Sie es . Nach dem Pigeonhole-Prinzip muss der DFA immer dann, wenn er eine Zeichenfolge liest, die länger als , einen Zustand zweimal besuchen: sagen wir den Zustand  . Nun ist  der Teil der Eingabe, der bis zum ersten Besuch von gelesen wurde (und diesen einschließt)  ,  ist der Teil, der nach dem ersten Besuch gelesen wurde, und bis einschließlich des zweiten (der mindestens ein Zeichen sein muss), und  ist der Rest . Aber jetzt können Sie sehen, dass akzeptiert werden muss: bringt Sie vom Startzustand zu ppqxqyzxzxq und Sie von in einen akzeptierenden Zustand. Ebenso muss für jedes positive akzeptiert werden  , da jede Wiederholung von  Sie von zurück zu  . Es ist zu beachten, dass die Zerlegung der Eingabe in , und  vollständig durch den Automaten bestimmt wird, der wiederum (aber nicht eindeutig) durch die Sprache bestimmt wird. Sie können also die Zerlegung nicht auswählen: Wenn die Sprache regulär ist, ist eine gewisse Zerlegung vorhanden. Um zu zeigen, dass eine Sprache nicht regulär ist, müssen Sie zeigen, dass jede Zerlegung fehlschlägt.zqxyiziyqqxyz

David Richerby
quelle
Dies ist eine gute Erklärung, aber ich verliere mich, nachdem ich cs.stackexchange.com/a/1051/10511 gelesen habe . Schauen Sie sich Punkt 4 an. Er überlegt, ob er die Zeichenfolge in drei Teilzeichenfolgen aufteilen soll. Ich lese es so, dass ich es auf jede Art und Weise pumpen kann, wie ich den String teile, vorausgesetzt, ich habe eine reguläre Sprache. Wo ist also der Fehler? Das nervt mich wirklich, dass ich es nicht verstehe. Bis zu dem Punkt, dass ich nachts nicht normal schlafen kann.
Flashburn
1
@flashburn Wenn es nicht regelmäßig sein soll, kann keine Aufteilung funktionieren. Hier finden wir eine , die funktioniert, daher können wir mit diesem Lemma nicht zeigen, dass sie nicht regelmäßig ist.
Raphael
@flashburn Ich habe eine Erklärung hinzugefügt, warum das Pump-Lemma wahr ist, die Ihnen das Verständnis erleichtern könnte, indem ich zeige, woher die Anforderungen des Lemmas stammen.
David Richerby
1
@flashburn Auch wenn Ihr Studium Sie so sehr belastet, dass Sie nicht richtig schlafen können, sollten Sie sich mit dem Beratungsdienst Ihrer Universität unterhalten. Das Pumping Lemma ist wichtig, aber Ihre Gesundheit und Ihr Wohlbefinden sind viel wichtiger.
David Richerby
2
Ganz zu schweigen davon, dass richtiger Schlaf, Ernährung und Bewegung Ihren Geist viel besser arbeiten lassen, @flashburn. Siehe auch hier .
Raphael