Class 19: Homework
You must print this sheet out and write/type answers on it!
-
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.
-
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.
-
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| ≤ _______.