**Sipser Exercise 1.49**

**(a)** **Theorem**: The language is a regular language.

*Proof*:
Notice that strings in must start with , since .
Also, any string of the form will certainly be in as long as contains at least one 1.
In other words, we have .
So, the following DFA accepts :

**(b)** **Theorem**: The language is not a regular language.

*Proof*:
Suppose were regular and let be the pumping length.
Take , noting that and .
Then let with and .

Because , and is a prefix of , it must be the case that and consist entirely of ’s. In particular, for some . But then , which is not in , contradicting the pumping lemma, so is not regular.