patternMinor
If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?
Viewed 0 times
myhillnonareallregularnerodelanguageclassesoversingletons
Problem
Is there a non-regular language over unary alphabet $\{a\}$ which has a Myhill-Nerode equivalence class that is not a singleton?
Solution
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.
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.
Context
StackExchange Computer Science Q#22272, answer score: 7
Revisions (0)
No revisions yet.