Proving that a derived language is regular Suppose I have a DFA recognizing a regular language $L$, how do I prove that 
$$\text{lefthalf}(L)= \{ w_1 \mid \exists w_2 \in \Sigma^* ,w_1w_2 \in L \land \|w_1\| = \|w_2\| \}$$ is also a regular language?
Hint: while reading $w_1$, guess $w_2$ and gather enough information so that in the end you can decide whether $w_1 w_2 \in L$.