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

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?

• What does "SW" mean? May 11 at 14:53
• "SW" comes from "SandWich", I guess. May 11 at 18:35
• Is it that $sw(\sigma)$ denote the "Shortest Word generated by $\sigma$ (if it exists) and if there are several, $sw(\sigma)$ is the lexicographically first of those"? Taken from Page-46 of this PDF. May 31 at 23:36

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.

• Hey Yuval, can you explain what exactly is $\delta_x(q)$? Toda! ;) Jun 17 at 9:34
• $\delta_x(q) = \delta(q,x)$. Jun 17 at 10:14
• Oh I missed that, thanks! Jun 17 at 10:15

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

• Nice! For me the interesting discovery is of course that the prefix/suffix string $x$ itself is no longer important, just the proper pairs $(q,q')$. Note that it is not necessary to explictly construct a new automaton if we use closure under union of regular languages for $A_{qq'}=(Q,\Sigma,\Delta,\{q\},\{q'\})$. May 11 at 20:52
• @HendrikJan Indeed -- the "summary" of the prefix/suffix string in $(q, q')$ is the key idea.
– 6005
May 12 at 4:25

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.