La preuve que

Montre CA $L=\{a^{n^2} | n \geq 0\}$ n'est pas régulier

Salut les gars. Je prends un cours de CS et ce truc est vraiment nouveau pour moi, alors soyez indulgent avec moi. J'ai essayé de voir si j'obtenais une contradiction en utilisant le lemme de pompage pour les langues régulières et j'ai travaillé comme ceci:

Supposer $L$est régulier. Ensuite, il doit y avoir un nombre naturel$m$ pour tous les mots $z$ dans $L$ avec longueur $|z| \geq m$ et il existe une décomposition $z = uvw, |uv| \leq m, |v| > 0$, pour que $u(v^i)w$ est dans la langue de tout $i \geq 0$.

Considérez la chaîne $a^{m^2}$.

alors $uv = a^{k^2} = a^{x+y}$, pour certains $k \leq m$ et $x = (k-1)^2$.
alors$v = a^y = a^{2k-1}$.

Laisser $i = 2$. alors$u(v^2)w = a^{x+2y}$. Mais$\sqrt{x+2y}$n'est pas nécessairement un nombre naturel -> Contradiction! Par conséquent,$L$ ne peut pas être régulier.

Eh bien, je sais que ce chemin est inutilement compliqué et vous pouvez le prouver différemment (je connais déjà la solution la plus simple). Mais ma question est la suivante: ma preuve est-elle également valable ou contient-elle un défaut? Est-ce formellement correct?

J'apprécie tout commentaire! Merci!

Vous ne pouvez pas en déduire $uv = a^{k^2}$, tout ce que le lemme de pompage vous donne, c'est que $|uv| \leq m$. Tous les nombres ne sont pas inférieurs à$m$sont des carrés. Non seulement cela, mais même en supposant que$uv = a^{k^2}$, il n'y a aucune raison de supposer que $v = a^{2k-1}$; tout le lemme de pompage vous donne est que$v$n'est pas vide. Enfin, pour obtenir une contradiction, il ne suffit pas que$x + 2y$ pas besoin d' être un carré, ça ne doit pas être un carré! Depuis$x$ et $x+y$ sont des carrés adjacents, il est en fait vrai que $x + 2y$ n'est pas un carré.