4
$\begingroup$

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

$\endgroup$

migrated from math.stackexchange.com Mar 4 '14 at 15:50

This question came from our site for people studying math at any level and professionals in related fields.

  • $\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 '14 at 15:53
7
$\begingroup$

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.

$\endgroup$
  • $\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 '14 at 23:15
  • $\begingroup$ @Patrick87 This is only true for languages over a unary alphabet! In general it's definitely not true. $\endgroup$ – Yuval Filmus Mar 5 '14 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 '14 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 '16 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 '16 at 0:22

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.