Consider the language L=\left\{0^{n} 1^{n}: n \in \mathbb{N}\right\}.
(a) Suppose D is a DFA with n states which decides L. Furthermore, let S be a set of consisting of k words w \in\{0,1\}^{*}. What is the smallest value of k such that for all such sets S, there exist two words in S which land in the same state at the end of the simulation? Provide brief justification.
(b) Using this, show that L is irregular, i.e. show that D does not exist. (Hint: how can you use the main idea of the previous problem to arrive at a contradiction?)