Sipser Exercise 1.57
Theorem: If is regular, then the language of left-halves of strings in A:
is also regular.
Proof: Since is regular, there is a DFA accepting . Write the states as . We construct an NFA as follows.
Take , and . We maintain a ‘prime’ copy of the DFA , which will start at . We then run other machines simultaneously. Each of these machines starts at a different state from , and takes all possible transitions at each step. Then an input string is accepted if and only if the ‘prime’ copy is in a state at the same time as the copy started from is in a final state.
So, we further define:
So this machine accepts , and is regular.