# Build an automaton from a given automaton to prove regularity of more complex strings

let $$L$$ be a regular language, and let $$A=\{\Sigma, Q, q_0, F, \delta\}$$ be a DFA such that $$L = L(A)$$.

I need to prove that $$L_p=\{xy\in\Sigma^*\mid\delta(q_0, y)=p\text{ and } \delta(p, x)\in F\}$$ is regular for every $$p\in Q$$ by defining an automaton $$A_p$$.

I tried to define it like so $$A_p=\{\Sigma, Q\times Q, (p, q_0), F\times \{p\}, \delta_p\}$$ where $$\delta_p$$ is defined like so $$\delta_p((q_1, q_2), \sigma) = (\delta(q_1, \sigma), q_2)\text{ if }q_1 \not\in F, \\ \delta_p((q_1, q_2), \sigma) = (q_1, \delta(q_2, \sigma))\text{ if }q_1 \in F.$$ But then I have a problem where $$x=uv$$, $$\delta(p, u)\in F$$ and $$\delta(p, x)\in F$$.

I thought maybe I define $$A_p$$ as a non-deterministic automaton and then $$\delta_p((q_1, q_2), \sigma) = \{(\delta(q_1, \sigma), q_2), (q_1, \delta(q_2, \sigma))\}.$$ However, word $$z=uwv$$ where $$\delta_p((p, q_0), u) = (p_1, q_0) \Longrightarrow \delta_p((p_1, q_0), w) = (p_1, p) \\ \Longrightarrow \delta_p((p_1, p), v) = (p_2, p), p_2\in F\times \{p\}$$ is accepted while it shouldn't be part of $$L_p$$

• Your language $L_p$ is the concatenation of the languages accepted by the automata $A_1=(\Sigma,Q,p,F,\delta)$ and $A_2=(\Sigma,Q,q_0,\{p\},\delta)$. Hence the construction you need is that of concatenating two automata. In this case with an extra step to make the state spaces disjoint. Apr 20 at 11:17
• Crosspost with this question on Math.StackExchange. Apr 22 at 12:37

Since how a word $$w$$ is recognized as a member of $$L_p$$ depends on a successful choice of partition of $$w$$ into a prefix ($$x$$) and a suffix ($$y$$) among many possible partitions, a DFA with $$\epsilon$$-moves that accepts $$L_p$$ should be easier to build than a DFA.
To distinguish whether a symbol is used as in $$x$$ or in $$y$$, we can employ two copies of $$A$$, one copy for reading $$x$$ and one copy for reading $$y$$. When the state after reading some $$x$$ is one of the final states of the first copy, switch to the initial state $$q_0$$ of the second copy optionally, continuing reading the remaining $$y$$. At the end of reading all input, accept if the second copy is at state $$p$$.
Two copies of $$A$$ can be built on the cartesian product $$Q\times \{1,2\}$$, where the copy index $$1$$ and $$2$$ indicates which copy of $$A$$.
Here is a DFA with $$\epsilon$$-moves that accepts $$L_p$$.
$$D_p=\{\Sigma, Q\times\{1,2\}, (p, 1), \{(p,2)\}, \mu\}$$, where $$\mu$$ is defined below. $$\quad\mu((q,1), \sigma) = (\delta(q, \sigma), 1)\quad\forall q \in Q,\ \sigma\in\Sigma,$$
$$\quad\mu((q,2), \sigma) = (\delta(q, \sigma), 2)\quad\forall q \in Q,\ \sigma\in\Sigma,$$
$$\quad\mu((f,1), \epsilon) = (q_0, 2)\quad\forall f \in F.$$
Note that when the copy index is fixed, $$D_p$$ behaves exactly as $$A$$.