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.