$\text{Myhill–Nerode theorem.}$ Refer to $\text{Question 51}.$Let $L$ be a language and let $X$ be a set of strings. Say that $X$ is $\text{pairwise distinguishable}$ by $L$ if every two distinct strings in $X$ are distinguishable by $L.$ Define the $\text{index of L}$ to be the maximum number of elements in any set that is pairwise distinguishable by $L.$ The index of $L$ may be finite or infinite.
- Show that if $L$ is recognized by a $\text{DFA}$ with $k$ states, $L$ has index at most $k.$
- Show that if the index of $L$ is a finite number $k,$ it is recognized by a $\text{DFA}$ with $k$ states$.$
- Conclude that $L$ is regular iff it has finite index. Moreover, its index is the size of the smallest $\text{DFA}$ recognizing it$.$
