For a regular language $A$ with an alphabet $\Sigma$, define an equivalence relation for strings $x,y \in \Sigma^*$ by $x\equiv_A y\Leftrightarrow \,\forall w\in \Sigma^*, xw, yw\in A$ or $xw, yw\not\in A$. Let $[x] := \{ y\in \Sigma^* : y\equiv_A x\}$ be the equivalence class of $x$ with respect to $A$ for any $x\in \Sigma^*$. Let $A$ and $B$ be two regular languages, and suppose they have the exact same set of equivalence classes (as defined above).

Prove or disprove that $A$ and $B$ are either equal or complements.

I think the statement is true. Let $A_1,\cdots, A_k$ be the equivalence classes of $\Sigma^*$ with respect to $A$ (there are finitely many by the Myhill-Nerode theorem). I'm not sure how to get a contradiction if I assume there's a string $x$ in $A$ but not in $B$ and a string $y$ in $A$ and $B$. Obviously both strings must belong to different equivalence classes of $B$, and hence $A$.


1 Answer 1


No, the statement is not true. The language defines the equivalence classes, but not the other way around. Each class can be totally within or totally outside the language. So with several classes we have some room to choose which classes are in and which classes are out the language. We have to be careful though, some choices will change the equivalence relation itself.


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.