Is there a non-regular language over unary alphabet $\{a\}$ which has a Myhill-Nerode equivalence class that is not a singleton?

  • $\begingroup$ Can you please incorporate all relevant constraints into the body of the question? (not just the title) In particular the focus on a unary alphabet. $\endgroup$
    – D.W.
    Mar 6, 2014 at 15:53

1 Answer 1


I'm guessing you are talking about Myhill-Nerode classes.

We can view $L$ as a subset of $\mathbb N$, since only the length of the word is important on $\{a\}$. Moreover two numbers $i,j$ are equivalent iff for any $n$, $i+n\in L$ iff $j+n\in L$. Assume there are $i<j$ equivalent, and let $k=j-i$. Then for any $n$, we have $n\in L$ iff $n \bmod k\in L$, since you can replace $j$ by $i$ as many times as you want. This means $L$ is regular, because it depends only of the congruence classes modulo $k$.

So the answer to your question is Yes: if $L$ is nonregular, all classes are singletons.

  • $\begingroup$ Wait, this isn't true, right? Consider $L = RS$ where $R = \{a, b\}$ and $S = \{ww^R \mid w \in \{a, b\}^*\}$. The strings $a$ and $b$ are equivalent with respect to the indistinguishability relation used by Myhill-Nerode; $L$ is a non-regular language and at least one equivalence class contains two things. Or am I missing something? $\endgroup$
    – Patrick87
    Mar 4, 2014 at 23:15
  • $\begingroup$ @Patrick87 This is only true for languages over a unary alphabet! In general it's definitely not true. $\endgroup$ Mar 5, 2014 at 1:34
  • $\begingroup$ @YuvalFilmus Ah, good catch. I didn't pay enough attention to the title and focused on the question body, which isn't specific to unary languages. Should really pay more attention. $\endgroup$
    – Patrick87
    Mar 5, 2014 at 21:15
  • $\begingroup$ Your general argument is correct, but I guess you made a mistake in the details or I did not understand your argument. As the right congruence just holds for adding words, but not "removing" them (and not $0^i \equiv_L \lambda$), we just have for $m > i$ that $m$ is equivalent to $i + (m-i)~\mbox{mod}~k$ or $0^m \equiv_L 0^{i + ((m-i)~\mbox{mod}~k}$, so each such element falls in one of the classes $[0^i], [0^{i+1}], \ldots, [0^{i+(k-1)}]$ and the elements $0^0, 0^1, \ldots, 0^{i-1}$ do not have to fall into of those classes. Nevertheless the same conclusion is reached. $\endgroup$
    – StefanH
    May 27, 2016 at 20:07
  • $\begingroup$ @Stefan No I think it's correct: if $a^3$ is equivalent to $a^5$, it means you can replace $a^5$ by $a^3$ in any context, so even removing two $a$'s is ok, and you get $a\equiv a^3$ for instance. $\endgroup$
    – Denis
    May 28, 2016 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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