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?


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$.

| cite | improve this answer | |
  • $\begingroup$ But how do we prove that their equivalence classes do not change for the complement of a Language L $\endgroup$ – User_1234 Dec 7 '14 at 0:55

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.