Michael Sipser Edition 3 Exercise 1 Question 69 (Page No. 93)

Question

Let $\sum=\{0,1\}.$ Let $WW_{k}=\{ww|w\in \sum^{*}$ and $w$ is of length $k\}.$

1. Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states.
2. Describe a much smaller $NFA$ for $\overline{WW_{k}},$ the complement of $WW_{k}.$