Do the following problems from Humphreys and Prest:
1.4#2
2.2#5
2.4#6

For the next and last two problems refer to the page Automaton complexity.

Prove that
4. $A(x_1,\ldots,x_k)\le k+1$ for all $k$.
5. $A(x_1,\ldots,x_k)\le k$ for $k\ge 3$.

6. Extra credit (up to 4% of the course): improve some of the $\le$ estimates on the table of complexities.

(I proved in class that $A(x_1,\ldots,x_k)\le k+2$ for all $k$.)

It is essential to write legibly and show your work. If your work is absent or illegible, and
at the same time your answer is not perfectly correct, then no partial credit can be awarded.
Completely correct answers which are given without justification may receive little or no credit.

During this exam, you are permitted to use calculators, notes, or books.

You are not allowed to collaborate with others, except on the extra credit problem.