Problem $4($Pumping Is not Enough$)$

$10$pts

Sipser $1\mathrm{.}54.$

Hint: For part $($a$),$ you're asked to show that a language is not regular. Unfortunately, as you

will see in part $($b$),$ you cannot show this via the pumping lemma alone. Use the pumping lemma

together with additional results from class to solve this problem. It may help to look at the solution

to Sipser $1\mathrm{.}46($b$)$ on page $98.$ For part $($b$),$ think of the pumping lemma as the game discussed in

problem $1.$ Show that for this language, there is a strategy for the adversary to always win.