**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:

And finally,

So this machine accepts , and is regular.