Sipser Exercise 1.40


Let be a language over and let:

We show that if is regular, is also regular.


Let be a DFA that accepts . We construct a machine that accepts .

will be identical to except for the final states, so let . Define the final states of :

So, is simply a machine that accepts strings that end up in a final state for which there is no additional path to any other final state. Then accepts , and is regular.