# Regular Languages and Separating Suffixes

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.

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$$.
• Very nice, so it indeed characterises regular languages. I think I would give it as two questions: 1) prove that $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.$ 2) Define the automaton formally. Jan 8, 2021 at 16:59