# How do I use the Myhill-Nerode theorem to show that a language is not regular?

My language is the repetition of 0 to a length that's a power of 2:

$L = \{ 0^k \mid k=2^n, n \geq 1 \}$

I want to know how to use the Myhill-Nerode theorem to show that this language is not regular.

This is my first attempt at doing this although I am confident that I am wrong:

$j, p = 2^h$ for 2 distinct values of $h$, $h \in \mathbb{N}$:

$a = 0^{j/2}$

$b = 0^{p/2}$

$c = 0^{j/2}$

$ac = 0^{j/2}0^{j/2} = 0^j$ is in my language since $j$ is of the form $2^n$

$bc = 0^{p/2}0^{j/2}$ is not guaranteed to be in my language for every $p$ and $j$, since $j \ne p$

Thus my language must not be regular since $ac$ is in it but $bc$ is not.

If you want to use Myhill-Nerode to show that a language is not regular, you need to prove that there are infinitely many equivalence classes.

Basically here, it suffices to prove that each $0^j$ is in a different class.

For instance $0^9$ and $0^{10}$ are not in the same class, because $0^90^7\in L$ while $0^{10}0^7\notin L$. Try to write the general proof for any $0^i$ and $0^j$ with $i\neq j$.

Just to make a more precise argument according to the definition below:

Myhill-Nerode Theorem: Given a language $$L \subseteq \Sigma^*$$, Suppose $$\forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^* ,L(xz) \neq L(yz))$$ where S is an infinite set. Then L is not a regular language.

For the given problem, We have $$L(w) =\{ 0^k | k = 2^n, n \geq 1\}$$.

Take $$S = L$$ (note: the set $$S$$ is infinite and not necessarily regular!).

Now take any two distinct elements from set $$S$$, $$x=0^{2^i}$$ and $$y=0^{2^j}$$, and take $$z=0^{2^{i+1}-2^{i}} = 0^{2^i}$$.

Then $$xz = 0^{2^i}.0^{2^i} = 0^{2^{i+1}} \in L$$. So $$xz \in L$$.

Now $$yz = 0^{2^i}.0^{2^j} = 0^{2^i+2^j}$$

Here, we have two cases:

case 1: if $$i > j$$: we have, $$yz = 0^{2^j.(2^{i-j}+1)} \notin L$$ since $$(2^{i-j}+1)$$ is odd.

case 2: if $$j > i$$: Similar to the previous argument we have, $$yz = 0^{2^i.(1+2^{j-i})} \notin L$$ since $$(2^{i-j}+1)$$ is odd. Thus, $$yz \notin L$$

Hence, we will get an infinite number of distinct quotients as $$S$$ is an infinite distinctive set.

Thus, $$L$$ is not regular.

(Remark: This can be extended to any language of the form $$\{a^{x^i}|i \geq 1 \wedge a \in \Sigma\}$$ for any $$x\in \mathbb{N}$$)