1
$\begingroup$

We have $\Sigma =\{0\}$ and $$L=\{0^{2^n} \mid n\ge 0\}$$ How to prove that $L$ is irregular by using Myhill–Nerode theorem?

At other languages with $\Sigma >1$ we can usually separate the word or something like this with combination and this how we can show that two words are not at the same equivalent class....
But what we can do at this case?

Here what I tried:
Assuming that $i\ne j$, then $0^{2^i+1}$ is not at the same equivalent class with $0^{2^j+1}$, why?
Let mark: $p$ - the amount of $0$'s that we need to add to $0^{2^i+1}$ to be $0^{2^{i+1}}$, $q$ - same thing but with $j$ instead of $i$.
Of course $p\ne q$, hence:
$0^p\in 0^{2^i+1}$ but $0^p\notin 0^{2^j+1}$.

I'd like to know if I'm right at my and I should continue or try a different way...

Thank you!

$\endgroup$
  • 1
    $\begingroup$ What have you tried? What makes you think you can't do the same thing here (separate two words and show they're not in the same equivalence class)? Have you tried working out the Myhill-Nerode equivalence classes? If you search on "unary" or "unary alphabet" on this site you'll find lots of related questions that should enable you to answer your own question. e.g., cs.stackexchange.com/q/22272/755, cs.stackexchange.com/q/164/755, cs.stackexchange.com/q/16293/755, cs.stackexchange.com/q/1031/755. $\endgroup$ – D.W. Dec 18 '15 at 18:36
  • 1
    $\begingroup$ @D.W. - Here I put what I tried so far... Please tell me if I'm right.... :-) Thank you! $\endgroup$ – stud1 Dec 18 '15 at 19:27
  • $\begingroup$ 1. The "I assume" part makes no sense. You start by assuming that the equivalence class of $\varepsilon$ is the entire language, but you don't show any justification or explanation why you think this is valid. Anyway, this assumption is false. 2. Then, you say "I try to show..." -- but you don't show us what you actually tried. So what did you try? Where did you get stuck? 3. I think you need to review Myhill-Nerode and do a bit more reading in your textbook. $\endgroup$ – D.W. Dec 18 '15 at 19:50
  • $\begingroup$ @D.W., thank you for your answer: About your answer - 1. I base it from one of the links that you gave me... 2. OK, I'll try again, I thought that you want to see just the idea of my proof... So I'll be really glad if you will guide my, at the links you gave me there are languages with $|\Sigma|>1$ (most of them, and it's doesn't help...). 3. I reed it many times but it doesn't help..... $\endgroup$ – stud1 Dec 18 '15 at 20:24
  • $\begingroup$ I saw something here: cs.stackexchange.com/questions/22272/… but I don't know how to use it... $\endgroup$ – stud1 Dec 18 '15 at 20:28
2
$\begingroup$

Your idea is basically correct, but your argument could be written in a clearer way. You want to say that if $i \neq j$ then $0^{2^i+1},0^{2^j+1}$ are inequivalent. You propose to consider adding the word $0^{2^i-1}$ to both, obtaining $0^{2^{i+1}},0^{2^i+2^j}$. The first word is clearly in $L$, whereas the second isn't, though an argument is required (left to you). This shows that the infinite set $\{0^{2^i+1} : i \geq 0\}$ consists of pairwise inequivalent words (modulo $L$), so $L$ is not regular.

In fact, all words $0^n$ are pairwise inequivalent modulo $L$ – see if you can prove that. (The argument is very similar.)

For languages over a unary alphabet there is a simpler characterization. Let $L = \{0^n : n \in I\}$. Then $L$ is regular if and only if $I$ is eventually periodic, which means that for some $m \geq 1$, $n + m \in I$ iff $n + 2m \in I$. The set of powers of two is not eventually periodic since it has arbitrarily large "gaps". (A formal argument is similar to your proof.)

$\endgroup$
  • 1
    $\begingroup$ This question is the first case I've seen in which the Pumping Lemma would actually be easier to use than Myhill-Nerode. ​ ​ $\endgroup$ – user12859 Dec 19 '15 at 3:23
  • $\begingroup$ Thank you for your answer and for your interesting explanation, but I'm stuck at the point that I need to show that $0^{2^{i+1}},0^{2^i+2^j}\notin L$ what if $j=2i$? Can you help me little bit with this? Great Thank you!! $\endgroup$ – stud1 Dec 19 '15 at 12:19
  • 1
    $\begingroup$ @stud1 I'm sure if you try hard enough you'll get it. Think of the binary representation of the integers involved. Note that there is nothing special about $j=2i$. $\endgroup$ – Yuval Filmus Dec 19 '15 at 14:13
  • $\begingroup$ Thank you Yuval!! I tried and I get it!! You helped me a lot!! :-) $\endgroup$ – stud1 Dec 19 '15 at 16:54

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.