Sipser Exercise 1.53


Let and

This language is not regular.


Proof: Suppose were regular and let be the pumping length. Take to be the string , noting that and . Then let such that and .

We see that and consist entirely of ’s, that is, for some . But is . Looking at the right-hand side, the sum must have in the ‘th spot, so this equation cannot be correct, and this string is not in , contradicting the pumping lemma. So is not regular.