0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Raphael Sep 18 '13 at 9:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

Hint: while reading $w_1$, guess $w_2$ from the end, and see where you meet in the middle. Thus you can take as the set of states a subset of $Q^2$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.