Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

It is well known that regular languages are characterized by the Myhill-Nerode equivalence. For language $L$ over $\Sigma^*$ define the equivalence $x\sim_L y$ over $\Sigma^*$ iff for all $z\in\Sigma^*$ we have $xz\in L \iff yz\in L$. Then $L$ is regular iff $\sim_L$ is of finite index, i.e., has a finite number of equivalence classes.

I know that the relation can be used to show that some languages are not regular, by indicating infinitely many strings that are not equivalent.

My question: can we easily use Myhill-Nerode to show closure properties of regular languages? Or should we use the "syntactic congruence" of languages?

As an example for prefix it is easy, as $x\sim_L y$ implies $x\sim_{\mbox{pref}(L)} y$. But how do we handle suffix, concatenation, star, mirror?

share|improve this question
add comment

1 Answer

The equivalence classes of the Myhill-Nerode relation are also the states of the minimal DFA for the language. So whatever is easy to show using DFAs, you can convert to a proof which uses the Myhill-Nerode point of view. Wherever you need NFAs, you can expect the proof to get more complicated.

But the correct answer is: try it out for yourself! That's how research is done.

share|improve this answer
Well, I was not asking for original research, thanks. I was hoping that someone knew whether the knowledge of $\sim_K$ being finite index would predict $\sim_{\phi(K)}$ being finite index, where $\phi$ is a language operation. I tried for $\phi$=prefix, but I cannot see how concatenation is handled in an elegant way. Yes, I can construct a decent DFA for it. –  Hendrik Jan Dec 16 '12 at 21:15
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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