# 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$$.
• Thank you for the reply. I understand why this works, since esentially $q_1 = q$ means we landed at $x$ and $q_2 \in F$ means $xy \in L$. However, I wanted to clarify what you mean by guessing $\tau$- these are epsilon transitions to other states in $A$ right? – user131539 Feb 3 at 19:12
• The NFA has no epsilon transitions (assuming you allow multiple initial states). You should advance $q_1$ and $q_2$ in parallel. – Yuval Filmus Feb 3 at 19:13
• Ok. So then every state in $A$ is an initial state, because a priori we have no idea where $x$ ends up in $A$? – user131539 Feb 3 at 19:18
• Right, $q$ could be any state of $A$. – Yuval Filmus Feb 3 at 19:57