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

| cite | improve this answer | |

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.