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.