Regularidad del medio exacto de las palabras de un lenguaje regular

Dejar $L$ser un lenguaje normal
Es el idioma$L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$ ¿regular?

Sé que es muy similar a la pregunta aquí , pero el problema es que no es una simple subcadena de una palabra en un idioma normal, sino más bien un "medio exacto": tenemos que contar el prefijo y la longitud del sufijo.

Por lo tanto, supongo que no es regular, pero no pude encontrar una manera de demostrarlo. Tampoco se me ocurrió ninguna forma de modificar el NFA de$L$ aceptar $L_2$.

Sugerencia: considere algunos DFA para $L$. Para cada$n \geq 0$, dejar $A_n$ ser el conjunto de estados $s$tal que hay alguna palabra de longitud$n$ que lleva el DFA desde el estado inicial a $s$. Dejar$B_n$ ser el conjunto de estados $t$tal que hay alguna palabra de longitud$n$ que lidera el DFA de $t$a un estado de aceptación. Finalmente, para cualesquiera dos estados$s,t$, dejar $R_{s,t}$ ser el conjunto (regular) de palabras que llevan a la DFA de $s$ a $t$. Tenemos

Dejar $D = (Q, Σ, δ, q_0, F)$ ser un DFA para $L$. Sin pérdida de generalidad, asuma$q_S, q_F \notin Q$. Construimos un ε-NFA$N = (Q ∪ \{q_S, q_F\}, Σ, Δ, q_S, \{q_F\})$ para $L_2$ de la siguiente manera:

Encuentra cada camino en $D$ desde $q_0$ a cualquier $f ∈ F$. Para cada camino$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}$ construir los caminos $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}$ para $0 \le i \le \frac{n_k}2$(es decir, construir todas las "partes intermedias" del camino). Esto se puede hacer de manera efectiva. Construir$Δ$ combinando todos estos caminos, junto con:

• $(q_S, ε, q_{k,i})$ para todos $i$ como anteriormente
• $(q_{k, n_k-i}, ε, q_F)$ para todos $i$ como anteriormente

$L(N)$ Es regular por construcción.

Bosquejo de prueba que $L(N) = L_2$: Dejar $w ∈ L(N)$. Por construcción sabemos que$w$ debe coincidir al menos en uno de los caminos $p_k^{(i)}$encima. Cada uno de este camino pertenece a un camino en$D$, que contiene un prefijo adicional y un sufijo de longitud $i$. Escoger$x$ como la palabra descrita por este prefijo y $y$el descrito por el sufijo Encontramos eso$xwy ∈ L$, con $|x| = |y| = i$. Con un razonamiento similar encontramos para cada$w ∈ L_2$ un camino en $N$. Dejar$i$ ser la longitud de $x$ y $y$ perteneciendo a $w$. $p_k^{(i)}$ para algunos $k$ formas $w$.

Así $L(N) = L_2$.