World's most popular travel blog for travel bloggers.

[Solved]: If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?

, , No Comments
Problem Detail: 

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

Asked By : Idan

Answered By : Denis

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22272

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback