Let $L$ be a regular language.
Is the language $L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$ regular?

I know it's very similar to the question here, but the catch is that it's not a simple substring of a word in a regular language, but rather an "exact middle" - we have to count the prefix and suffix length.

Therefore, I assume it's not regular, but I couldn't find a way to prove it. I also couldn't think of any way to modify the NFA of $L$ to accept $L_2$.

  • $\begingroup$ "exact middle" seems to suggest $|x|=|y|=|z|$? By the way, that will be regular too! $\endgroup$ – Hendrik Jan Apr 4 '13 at 20:24
  • $\begingroup$ Have you tried the stuff from our reference question? $\endgroup$ – Raphael Apr 4 '13 at 23:22

Hint: Consider some DFA for $L$. For every $n \geq 0$, let $A_n$ be the set of states $s$ such that there is some word of length $n$ which leads the DFA from the initial state to $s$. Let $B_n$ be the set of states $t$ such that there is some word of length $n$ which leads the DFA from $t$ to an accepting state. Finally, for any two states $s,t$, let $R_{s,t}$ be the (regular) set of words leading the DFA from $s$ to $t$. We have $$ L_2 = \bigcup_{n \geq 0} \bigcup_{\substack{s \in A_n \\ t \in B_n}} R_{s,t}. $$ Since there are only finitely many possibilities for $s,t$, the union is in fact finite, and so regular.


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

  • $\begingroup$ Since there are infinitely many paths, the remark "This can be done effectively" seems to need some explanation. Note that it is not strictly needed to use that property, see the answer by Yuval, which (to me) is a "noneffective" version of the same argument. $\endgroup$ – Hendrik Jan Apr 4 '13 at 20:22
  • $\begingroup$ You are right. You do not need to consider loops twice. The next critical point seems to be there is some $p_k^{(i)}$ belonging to $w$, as with combining the paths there could emerge new paths. You see I have not thorough reviewed my proof, but I believe all these issues could be solved. $\endgroup$ – ipsec Apr 5 '13 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.