9
$\begingroup$

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

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

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.

$\endgroup$
4
  • $\begingroup$ How is this a finite union given that we are unioning over $n \geq 0$? $\endgroup$
    – actinidia
    Sep 21 at 10:55
  • 1
    $\begingroup$ Since there are only finitely many possibilities for $A_n,B_n$. $\endgroup$ Sep 21 at 15:15
  • $\begingroup$ I'm not sure I follow. I get that the set of possibilities for $A_n, B_n$ are finite for fixed $n$, but there are an infinite number of possibilities for $n$ itself, and from what I understand an infinite union of regular languages need not be regular. $\endgroup$
    – actinidia
    Sep 26 at 6:28
  • $\begingroup$ Let $Q$ be the set of states of the DFA for $L$. Then $A_n$ and $B_n$ are both subsets of $Q$. The set $Q$ is finite, and so has finitely many subsets. $\endgroup$ Sep 26 at 6:58
3
$\begingroup$

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

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