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
xykz 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
xykz 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 xykz is accepted
by the machine for all k and y ≠ λ) for which |xy| ≤ _______.