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