All prefixes with same length as their suffix is a regular language Suppose $L$ is a regular language over $\Sigma$ and we want to show that $$\frac{1}{2}L = \{x \in \Sigma^* \mid \exists y \in \Sigma^* (xy\in L \wedge |x| = |y|)\}$$ is regular. I thought of taking the set of even length strings over $\Sigma^*$ (given by $(00\cup01\cup10\cup11)^*$) and then interescting with $L$, which would be regular because the intersection of regular languages is regular. Then, the set of prefixes of this language is regular (by a previous exercise), but that's useless because that set of strings isn't actually the set $\frac{1}{2}L$. In particular, we didn't constrain the prefixes to be the ones with equal length suffixes.
Baically, I'm really stuck on how to make a FA that recognizes the length of the strings. Namely, given $x$ how do we add $\epsilon$ transitions to arrive at $xy$ with $|x| = |y|$, which we then pass in $xy$ to the FA for $L$? Thanks in advance, I've been scratching my head on this for a while.
Given a DFA $A$ for $L$, construct an NFA which operates as follows:

The NFA starts by guessing a state $q$ which will be the state that $A$ is on after reading $x$.
The NFA will maintain two states, $q_1,q_2$, the first initialized at the initial state of $A$, the second initialized at $q$.
For each symbol $\sigma$ read, the NFA guesses a new symbol $\tau$ (which corresponds to a symbol in $y$), and advance $q_1$ using $\sigma$ and $q_2$ using $\tau$.
The NFA is at an accepting case if $q_1 = q$ and $q_2$ is an accepting state of $A$.