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.