If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$

Question

For a language $\mathcal{L}$ over an alphabet $\Sigma$, define

$$\mathcal{SW(L)} := \{ y ∈ Σ^∗ \mid \exists x \in Σ^* \text{ such that } xyx \in \mathcal{L}\}$$

How can I prove that if $\mathcal{L}$ is regular, then $\mathcal{SW(L)}$ is also regular?

Answer 1

Take a DFA $(Q,\Sigma,\delta,q_0,F)$ accepting $\mathcal{L}$. We can associate each word $x \in \Sigma^*$ with a function $\delta_x\colon Q \to Q$ given by $\delta_x(q) = \delta(q,x)$. In other words, if the DFA is at state $q$ and it reads the word $x$, then it reaches state $\delta_x(q)$. Let $\Delta = \{ \delta_x : x \in \Sigma^* \}$.

A word $y$ is in $\mathcal{SW}(\mathcal{L})$ if there exists $x \in \Sigma^*$ such that $(\delta_x \circ \delta_y \circ \delta_x)(q_0) \in F$. Hence in order to determine whether $y \in \mathcal{SW}(\mathcal{L})$, it suffices to maintain $\delta_y$, which can be done using a DFA whose set of states is $Q^Q$. I leave the rest of the details to you.

Answer 2

Idea: Suppose we have an NFA $(Q, \Sigma, \Delta, I, F)$ for $\mathcal{L}$. To build an NFA for $\text{SW}(\mathcal{L})$, our plan is to make a separate copy of the states of the NFA for each candidate start state $q$, where that machine reads in $y$ and checks whether it is possible for some $x$ to (i) get from an initial state $I$ to the candidate start state $q$ on $x$, (ii) get from $q$ to $q'$ on $y$, and (iii) read in the same string $x$ to get from $q'$ to an accepting state in $F$. Formally, the states of the new NFA are $Q \times Q$ (one copy of $Q$ for each possible start state $q \in Q$), and our new NFA is $$ (Q \times Q, \Sigma, \Delta', \{(q, q) \mid q \in Q\}, F') $$ where $F'$ is defined formally as $$ F' = \{(q, q') \in Q \times Q \mid \exists x: q \in \Delta(I, x) \text{ and } \Delta(q', x) \cap F \ne \varnothing. $$

Note that the set $F'$ is a finite set -- we can just enumerate all the pairs in $Q \times Q$ and determine whether they are in $F'$ or not.

The definition of $\Delta'$ will be straightforward as it is the same for each copy of the original automaton.

Then we have to carefully argue two things (left as an exercise):

1. If $w \in \text{SW}(\mathcal{L})$, then there is an accepting run of the new automaton on $w$.

2. If there is an accepting run of the new automaton on $w$, then $w \in \text{SW}(\mathcal{L})$.

Answer 3

If $L$ is a language of $A^*$ and $u, v$ are words, let $$ u^{-1}Lv^{-1} = \{ x \in A^* \mid uxv \in L \} $$ It is a well-known fact that if $L$ is regular, then every language $u^{-1}Lv^{-1}$ is regular and the set $\{u^{-1}Lv^{-1} \mid u, v \in A^*\}$ is finite. In particular, the subset $\{u^{-1}Lu^{-1} \mid u \in A^*\}$ is finite. Now observe that $$ SW(L) = \bigcup_{u \in A^*} u^{-1}Lu^{-1} $$ to conclude that $SW(L)$ is regular.