Beweis, dass

Zeigen Sie, dass ist nicht regulär$L=\{a^{n^2} | n \geq 0\}$

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 .$L$$m$$z$$L$$|z| \geq m$$z = uvw, |uv| \leq m, |v| > 0$$u(v^i)w$$i \geq 0$

Betrachten Sie die Zeichenfolge .$a^{m^2}$

Dann ist für einige und . Dann ist .$uv = a^{k^2} = a^{x+y}$$k \leq m$$x = (k-1)^2$
$v = a^y = a^{2k-1}$

Sei . Dann ist . Aber ist nicht unbedingt eine natürliche Zahl -> Widerspruch! Daher kann nicht regelmäßig sein.$i = 2$$u(v^2)w = a^{x+2y}$$\sqrt{x+2y}$$L$

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!

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, dass$uv = a^{k^2}$$|uv| \leq m$$m$$uv = a^{k^2}$$v = a^{2k-1}$$v$$x + 2y$ $x$$x+y$$x + 2y$ kein Quadrat ist.