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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Welcome to Computer Science! Your question is a very basic one. Since you did not include much of an attempt to solve it on your own, we have little to work with. Let me direct you towards our reference questions which cover your problem in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Your question may then be reopened. Good luck! $\endgroup$– RaphaelCommented Sep 18, 2013 at 9:31
-
$\begingroup$ @Raphael The question cs.stackexchange.com/questions/1331/… is not the same as this one. I would prefer to refer to this question cs.stackexchange.com/questions/11018/… $\endgroup$– J.-E. PinCommented Sep 19, 2013 at 5:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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$.
answered Sep 18, 2013 at 6:38
$\begingroup$
$\endgroup$
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$.
