# If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?

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

• 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. – D.W. Mar 6 '14 at 15:53

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.
• 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? – Patrick87 Mar 4 '14 at 23:15
• 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. – StefanH May 27 '16 at 20:07
• @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. – Denis May 28 '16 at 0:22