Automata|The mid 1/3 of regular language is still regular Define $$L_{\frac{1}{3}}=\{w \in \Sigma^*\ |\ \exists x,y\in \Sigma^*,\ xwy\in L,\ |x|=|w|=|y|\}$$L is a regular language, is $L_{\frac{1}{3}}$ a regular language?
I think it might be similar to the question of half of L. Automata | Prove that if $L$ is regular than $half(L)$ is regular too But I find it hard to build an automaton like that.
 A: A powerful method to prove this result (and many similar ones) is to use the fact that a language is regular if and only if it is recognized by a finite monoid. A language $L$ of $A^*$ is recognized by a finite monoid $M$ if there is a surjective monoid morphism
$f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$.
Let $\mathcal{P}(M)$ be the monoid of subsets of $M$, with product defined, for each $X, Y \in \mathcal{P}(M)$, by
$$
  XY = \{xy \mid x \in X, y \in Y\}
$$
Let now $N$ be the commutative submonoid of $\mathcal{P}(M)$ generated by $f(A)$. I claim that $L_{1/3}$ is recognized by $M \times N$ and hence is regular.
Indeed, let $g: A^* \to M  \times N$ be the monoid morphism defined, for each letter $a \in A$, by $g(a) = (f(a), f(A))$. Thus, for each word $u \in A^*$, 
$$
g(u) = (f(u), f(A)^{|u|})
$$
Setting
$$
  Q = \{ (m,R) \in M \times N \mid RmR \cap P \not= \emptyset \},
$$
one gets 
\begin{align}
 g^{-1}(Q) &= \{ u \in A^* \mid g(u) \in Q \} =  \{ u \in A^* \mid f(A)^{|u|}f(u)f(A)^{|u|} \cap P \not= \emptyset \}\\
 &= \{ u \in A^* \mid f(A^{|u|}uA^{|u|}) \cap P \not= \emptyset \} 
= \{ u \in A^* \mid (A^{|u|}uA^{|u|}) \cap f^{-1}(P) \not= \emptyset \} \\
    &= \{ u \in A^* \mid A^{|u|}uA^{|u|} \cap L\not= \emptyset \}\\
 &= L_{1/3}
 \end{align}
which proves the claim.
