patternMinor
If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
Viewed 0 times
midregularthenexistsxyx
Problem
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?
$$\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?
Solution
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.
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.
Context
StackExchange Computer Science Q#151456, answer score: 4
Revisions (0)
No revisions yet.