Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

## Problem 1

Given the machine

*M*
write down 3 different ways the string

*ababaaabb* can be
"pumped", i.e. 3 different ways it can be broken up into
strings

*x*,

*y* and

*z* such that

*w = xyz*, and

*xy*^{k}z is accepted
by the machine for all

*k*. In each of
these,

*y* must correspond to traversing a loop in
the computation.

## Problem 2

For each of the following strings, write down the
decomposition into

*xyz* such that

*xy*^{k}z is accepted
by the machine

*M* for all

*k* for which

*xy* is
as short as possible. Once again, in each of
these,

*y* must correspond to traversing a loop in
the computation.

## Problem 3

Fill in the blank:
For any DFA *M = (Q,Σ,δ,s,W)* and string
*w*, where *|w| ≥ |Q|*, we can always
find a decomposition *w = xyz* (where *xy*^{k}z is accepted
by the machine for all *k* and *y ≠ λ*) for which *|xy| ≤ _______*.