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| ≤ _______.