Wie beweisen Sie dieses pumpende Lemma -Beispiel? [abgeschlossen

Question

Ich habe diese Frage bei meinem Test falsch verstanden und mich gefragt, ob jemand sie erklären könnte, und zeigte die Schritte, die unternommen wurden, um zum Schluss zu kommen. Jede Hilfe wäre geschätzt.

Im PL -Beweis für l_neq = {0^i1^j | I <j} Bei einem M-State-DFA wählt jemand die Zeichenfolge 0^(m/2) 1^(m/2+1). Sie wählen dann y = 0 und zeigen, dass wir durch Pumpen zu der Zeichenfolge 0^(m/2+1) 1^(m/2+1) ankommen können, die außerhalb von L_Neq liegt. Ist dieser Beweis korrekt? Warum oder warum nicht?

Wenn dieser Beweis falsch ist, schreiben Sie einen korrekten Beweis auf.

Vielen Dank

Answer 1

Wenn Sie das pumpende Lemma verwenden, dürfen Sie die Schnur zum Pumpen auswählen (nennen wir es w), sind Sie es nicht Erlaubnis zu wählen, wie man W in drei Teile xyz aufteilt. Stattdessen müssen Sie das für das zeigen irgendein Wie W in XYZ aufgeteilt werden könnte, gibt es eine Wahl von I, so dass xy^ichz so dass xy^ichz ∉ l_Neq. Während Sie Recht haben, wenn y = 0 ist, kann die Zeichenfolge aus L herausgenommen werden_Neq, Sie können nicht garantieren, dass y = 0. Stattdessen müssten Sie das für jede Wahl von Y zeigen, dass | xy | ≤ m und | y | > 0, Sie können die Zeichenfolge aus der Sprache herausnehmen.

Versuchen Sie als Hinweis die Zeichenfolge 0^m1^m. Jetzt für jede Wahl von y, da | xy | ≤ m, Sie wissen, dass y die Form 0 haben muss^j Für einige natürliche Zahl j> 0. Ihr Argument kann dann verwendet werden, um das XY zu zeigen^ichz ist nicht mehr in l_Neq.

Für eine weitere Ressource auf dem pumpenden Lemma und der Funktionsweise dieser Beweise können Sie sich gerne auschecken Diese Vorlesungsreihen Ich habe dieses Quartal in einer Theorie des Berechnungskurs früher verwendet. Sie gehen durch ein paar pumpende Lemma -Beispiele und zeigen (wichtige) das Gegneres Modell zum Nachdenken über diese Beweise.

Hoffe das hilft!