Prova de que não é regular

Mostre que não é regular$L=\{a^{n^2} | n \geq 0\}$

Ei pessoal. Eu estou tendo uma aula de CS e esse material é realmente novo para mim, então tenha paciência comigo. Tentei verificar se havia alguma contradição usando o lema de bombeamento para idiomas regulares e resolvi-o assim:

Suponha que seja regular. Então deve haver um número natural para todas as palavras em com comprimento existe uma decomposição , de modo que esteja no idioma para qualquer .$L$$m$$z$$L$$|z| \geq m$$z = uvw, |uv| \leq m, |v| > 0$$u(v^i)w$$i \geq 0$

Considere a sequência .$a^{m^2}$

Em seguida, , para alguns e . Então .$uv = a^{k^2} = a^{x+y}$$k \leq m$$x = (k-1)^2$
$v = a^y = a^{2k-1}$

Seja . Então . Mas não é necessariamente um número natural -> Contradição! Portanto, não pode ser regular.$i = 2$$u(v^2)w = a^{x+2y}$$\sqrt{x+2y}$$L$

Bem, eu sei que esse caminho é desnecessariamente complicado e você pode provar isso de maneira diferente (eu já sei a solução mais simples). Mas minha pergunta aqui é: minha prova também é válida ou contém alguma falha? Está formalmente correto?

Agradeço qualquer feedback! Obrigado!

Você não pode deduzir isso $uv = a^{k^2}$, tudo o que o lema de bombeamento fornece é que $|uv| \leq m$. Nem todos os números são menores que$m$são quadrados. Não apenas isso, mas mesmo supondo que$uv = a^{k^2}$, não há razão para supor que $v = a^{2k-1}$; todo o lema de bombeamento dá é que$v$não está vazio. Finalmente, para obter uma contradição, não basta que$x + 2y$ não precisa ser um quadrado, não deve ser um quadrado! Desde a$x$ e $x+y$ são quadrados adjacentes, é verdade que $x + 2y$ não é um quadrado.