Sipser Exercise 1.29


Theorem: The language is not regular.


Proof: Suppose were regular and let be the constant guaranteed by the pumping lemma. Take , noting that and . Then let such that 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.