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}$)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.