Menu

Class 19: Homework


You must print this sheet out and write/type answers on it!

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