Prove that the following language is not regular by using the Myhill-Nerode Relation

301 Views Asked by At

$A_3=\{a^{2^n}|n \geq 0\}$ and the alphabet is the set with the element $a$, so it's just the language whose members length are a power of 2.

Proof: Let $x=\{a^i |i \geq0\}$ and $z=a^j$ where j is odd. If $i$ is odd then there exists a way $i+j$ can be a power 2. We will pick these pairs of i,j, so $a^ia^j \in A_3$, but if $i$ is even, this $j$ will never make the string be in the language because string length is always odd, so in this case $a^ia^j \notin A_3$. Therefore, z is an distinguishable string which implies $A_3$ is not regular.

I am not sure if this is complete because I think I am being a little bit inaccurate by generating the desired powers of two. Can this proof be sufficient?

1

There are 1 best solutions below

5
On

In order to use the Myhill-Nerode theorem to prove non-regularity, you must find an infinite set of mutually distinguishable strings (i.e., any 2 strings in the set are distinguishable). You haven't done that; at best, your argument only shows that $a^i$ for $i$ odd is distinguishable from $a^i$ for $i$ even. That only gets you 2 distinguishable strings, but you need infinitely many.