Using Myhill Nerode

Question

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?

score 2 · Accepted Answer · answered Jun 29 '15 at 20:25

2

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$?

answered Jun 29 '15 at 20:25

Brian M. Scott

616,228

Ah thanks a lot! To get it clear, this is what you're saying? : $a^ia^{k^2-i}$ is in L, but $a^ja^{k^2-i}$ is not? – Steven Jun 29 '15 at 20:45
@Steven: Yes, when $k$ is chosen to be larger than $j-i$. You’re welcome! – Brian M. Scott Jun 29 '15 at 20:46

Using Myhill Nerode

1 Answers1