Let $D = (Q, Σ, δ, q_0, F)$ be a DFA for $L$. Without loss of generality, assume $q_S, q_F \notin Q$. We construct a ε-NFA $N = (Q ∪ \{q_S, q_F\}, Σ, Δ, q_S, \{q_F\})$ for $L_2$ the following way:
Find each path in $D$ from $q_0$ to any $f ∈ F$. For each such path $p_k: q_0 = q_{k,0} \xrightarrow{α_{k,1}} q_{k,1} \xrightarrow{α_{k,2}} … \xrightarrow{α_{k,i}} q_{k,i} \xrightarrow{α_{k,i+1}} … \xrightarrow{α_{k,n_k}} q_{k,n_k}$ construct the paths $p_k^{(i)} : q_{k,i} \xrightarrow{α_{k,i+1}} q_{k,i+1} \xrightarrow{α_{k,i+2}} … \xrightarrow{α_{k,n_k-i}} q_{k,n_k-i}$ for $0 \le i \le \frac{n_k}2$ (i.e. constuct all “middle parts“ of the path). This can be done effectively.
Construct $Δ$ by combining all these paths, together with:
- $(q_S, ε, q_{k,i})$ for all $i$ as above
- $(q_{k, n_k-i}, ε, q_F)$ for all $i$ as above
$L(N)$ is regular by construction.
Proof sketch that $L(N) = L_2$:
Let $w ∈ L(N)$. By construction we know that $w$ must match at least on of the paths $p_k^{(i)}$ above. Each of this path belongs to a path in $D$, which contains an additional prefix and suffix of length $i$. Choose $x$ as the word described by this prefix and $y$ the one described by the suffix. We find that $xwy ∈ L$, with $|x| = |y| = i$. With similar reasoning we find for each $w ∈ L_2$ a path in $N$. Let $i$ be the length of $x$ and $y$ belonging to $w$. $p_k^{(i)}$ for some $k$ forms $w$.
Thus $L(N) = L_2$.