Beweis, dass

8

Zeigen Sie, dass ist nicht regulärL={an2|n0}

Hallo Leute. Ich nehme an einem CS-Kurs teil und dieses Zeug ist wirklich neu für mich. Ich habe versucht herauszufinden, ob ich einen Widerspruch bekomme, indem ich das Pump-Lemma für reguläre Sprachen verwende, und ich habe es so ausgearbeitet:

Angenommen, ist regulär. Dann muss es für alle Wörter in mit der Länge eine natürliche Zahl und es existiert eine Zerlegung , so dass in der Sprache für jedes .LmzL|z|mz=uvw,|uv|m,|v|>0u(vi)wi0

Betrachten Sie die Zeichenfolge .am2

Dann ist für einige und . Dann ist .uv=ak2=ax+ykmx=(k1)2
v=ay=a2k1

Sei . Dann ist . Aber ist nicht unbedingt eine natürliche Zahl -> Widerspruch! Daher kann nicht regelmäßig sein.i=2u(v2)w=ax+2yx+2yL

Nun, ich weiß, dass dieser Weg unnötig kompliziert ist und Sie ihn anders beweisen können (ich kenne bereits die einfachste Lösung). Aber meine Frage hier ist: Ist mein Beweis auch gültig oder enthält er einen Fehler? Ist es formal korrekt?

Ich freue mich über jedes Feedback! Vielen Dank!

Gilles 'SO - hör auf böse zu sein'
quelle
1
Zu Ihrer Information - Reguläre Ausdrücke, wie sie in der theoretischen Informatik definiert sind, und reguläre Ausdrücke, die Programmierer verwenden, sind verwandt, aber sehr unterschiedlich.
2
Sie scheinen einige der klassischen Fehler bei der Anwendung des Pumping-Lemmas gemacht zu haben. Bitte beachten Sie unsere Referenzfrage für eine detaillierte Erklärung und ein Beispiel.
Raphael
Das ist nicht richtig, nein. Ihr Argument kann nicht von der Annahme abhängen, dass . uv=ak2
Patrick87

Antworten:

8

Sie können nicht ableiten, dass , alles, was das Pump-Lemma Ihnen gibt, ist das . Nicht alle Zahlen unter sind Quadrate. Nicht nur das, sondern auch wenn angenommen wird, dass , gibt es keinen Grund anzunehmen, dass ; Alles, was das Pump-Lemma Ihnen gibt, ist, dass nicht leer ist. Um einen Widerspruch zu erhalten, reicht es schließlich nicht aus, dass kein Quadrat sein muss, sondern kein Quadrat! Da und benachbarte Quadrate sind, ist es tatsächlich so, dassuv=ak2|uv|mmuv=ak2v=a2k1vx+2y xx+yx+2y kein Quadrat ist.

Yuval Filmus
quelle
Irgendwelche Hinweise, wie man den Beweis behebt?
Raphael
Das OP "kennt bereits die einfachste Lösung", von der ich annehme, dass sie dem festen Beweis entspricht.
Yuval Filmus
@ YuvalFilmus Nicht unbedingt. Es gibt einen ziemlich einfachen Beweis mit dem Myhill-Nerode-Theorem, der nichts mit dem Pump-Lemma zu tun hat. Dies könnte derjenige sein, auf den sich das OP bezieht.
Patrick87