Given language $L$, I want to show that its Myhill-Nerode equivalence classes are the same as for its complement $\overline{L}$.

I am thinking of constructing a DFA $M$ for the Language $L$ so the DFA for the language of its complement will be just changing the final states to non final states but the states will be same. So the classes do remain same? How do I put this in a more formal way?


1 Answer 1


Note that the Myhill-Nerode equivalences are also defined for non-regular languages, so constructing a finite state automaton will not help.

What is the definition of such a class? $x \sim_L y$ iff $xz\in L$ whenever $yz\in L$ (for any string $z$). How does that change when we consider the complement of $L$? We use basic logic: $P\Leftrightarrow Q $ iff $\lnot P\Leftrightarrow \lnot Q $.

$x \sim_L y$ iff
$xz\in L$ whenever $yz\in L$ (for any string $z$) iff
(not $xz\in L$) whenever (not $yz\in L$) (for any string $z$) iff
$xz\in \bar L$ whenever $yz\in \bar L$ (for any string $z$) iff
$x \sim_{\bar L} y$.

  • $\begingroup$ But how do we prove that their equivalence classes do not change for the complement of a Language L $\endgroup$
    – User_1234
    Commented Dec 7, 2014 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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