Regular Languages and Separating Suffixes

Question

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.

Answer 1

For $\sigma \in \Sigma$, let $f_\sigma$ be the indicator function of $L_{\epsilon,\sigma}$, let $f$ be the indicator function of $L$, and let $b$ be the indicator of $\epsilon \in L$. If $w = \sigma_1 \ldots \sigma_n$ then $$ f(w) = f_{\sigma_1}(\sigma_2 \ldots \sigma_n) \oplus f_{\sigma_2}(\sigma_3 \ldots \sigma_n) \oplus \cdots \oplus f_{\sigma_n}(\epsilon) \oplus b. $$ Imagine a finite automaton reading the word in reverse (we know that regular languages are closed under reversal). The finite automaton maintains an accumulator $a$ initialized by $b$, and states of DFAs for the reverses of $L_{\epsilon,\sigma}$ for all $\sigma \in \Sigma$. When reading $\sigma_i$, it updates $a$ by $a \oplus f_{\sigma_i}(\sigma_{i+1} \ldots \sigma_n)$, and then updates the states of all DFAs. Finally, it accepts if $a = 1$.