Preparing for the next semester, I wanted to give the following as a homework question, yet after a few attempts, I failed to solve it.
Given a language $L\subseteq \Sigma^*$ and two words $x,y\in \Sigma^*$, define the language $L_{x,y}$ consisting of all the separating suffixes of the words $x,y$ relative to the Myhill-Nerode relation of $L$. That is, $$L_{x,y} = \{ z\in \Sigma^*: (xz\in L \wedge yz\notin L) \lor (xz\notin L \wedge yz\in L) \}$$ Is it true that if $L_{x,y}$ is regular for every $x,y \in \Sigma^*$ then $L$ is regular?
Thoughts:
The solution I had in mind works only for languages that have bad prefixes. A word $y$ is a bad prefix for $L$ if you cannot extend $y$ to a word in $L$. That is, $y\cdot z \notin L$ for every $z \in \Sigma^*$. If $y$ is a bad prefix for $L$, then $L = L_{\epsilon,y}$, and so if $L_{\epsilon,y}$ is regular, we're done. But clearly, some languages don't have bad prefixes.
The opposite claim is correct: if $L$ is regular, then $L_{x, y}$ is regular. This can be easily solved as follows. If $A = \langle Q, \Sigma, q_0 , \delta, F \rangle$ is a DFA for $L$, then one can define a DFA $B$ for $L_{x, y}$ over the product of $A$ with itself: $B = \langle Q^2, \Sigma, \langle \delta(q_0, x), \delta(q_0, y) \rangle, \delta', ((Q\setminus F) \times F) \cup (F \times (Q\setminus F))\rangle$. I omit the details.