1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 8 at 16:59
  • $\begingroup$ That would be a nice exercise! $\endgroup$ Jan 8 at 19:17

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.