I'm trying to prove to following language is not regular, using Myhill Nerode's theorem:
$L = {a^{n^2}}$
I found this:
$a^n$ (has no equivalence classes to) $a^m$ when n ≠ m because
$a^na^n$ is in L but $a^ma^n$ is not in L, which implies that L has infite equivalence classes. Is this right?
That doesn’t actually work: $a^na^n=a^{2n}$ is not necessarily in $L$. However, it’s true that if $m\ne n$, then $a^m$ and $a^n$ have a distinguishing extension. Suppose that $m<n$, and let $d=n-m$. Let $k$ be any integer such that $k\ge d$ and $k^2\ge m$, and let $\ell=k^2-m$. Then $a^ma^\ell=a^{m+\ell}=a^{k^2}\in L$. Now show that $n+\ell=m+d+\ell=k^2+d$ cannot be a perfect square, and conclude that $a^na^\ell\notin L$. HINT: What is $(k+1)^2$?