Question 1.52: Myhill–Nerode theorem. Refer to Problem 1.51. Let L be a lan...
Myhill–Nerode theorem. Refer to Problem 1.51. Let L be a language and let X be a set of strings. Say that X is pairwise distinguishable by L if every two distinct strings in X are distinguishable by L. Define the 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.
a. Show that if L is recognized by a DFA with k states, L has index at most k.
b. Show that if the index of L is a finite number k, it is recognized by a DFA with k states.
c. Conclude that L is regular iff it has finite index. Moreover, its index is the size of the smallest DFA recognizing it.
(a) We prove this assertion by contradiction. Let M be a k-state DFA that recognizes L. Suppose for a contradiction that L has index greater than k. That means some set X withmore than k elements is pairwise distinguishable by L. BecauseM has k states, the pigeonhole principle implies that X contains two distinct strings x and y, where \delta (q_{0},x) = \delta (q_{0},y). Here \delta (q_{0},x) is the state that M is in after starting in the start state q_{0} and reading input string x. Then, for any string z \in \Sigma ^{*}, \delta (q_{0}, xz ) = \delta (q_{0}, yz ). Therefore, either both xz and yz are in L or neither are in L. But then x and y aren’t distinguishable by L, contradicting our assumption that X is pairwise distinguishable by L.
(b) Let X = \left\{s_{1},…,s_{k} \right\} be pairwise distinguishable by L. We construct DFA M = (Q, \Sigma ,\delta ,q_{0}, F ) with k states recognizing L. Let Q = \left\{q_{1},…,q_{k} \right\}, and define \delta = (q_{i},a ) to be q_{j}, where s_{j} \equiv L s_{i} a (the relation ≡ L is defined in Problem 1.51). Note that s_{j} \equiv L s_{i} a for some s_{i}\in X; otherwise, X \cup s_{i} a would have k + 1 elements and would be pairwise distinguishable by L, which would contradict the assumption that L has index k. Let F = \left\{q_{i}\mid s_{i} \in L \right\}. Let the start state q_{0} be the q_{i} such that s_{i}\equiv L \epsilon. M is constructed so that for any state q_{i}, \left\{s\mid \delta (q_{0},s )=q_{i} \right\} = \left\{s\mid s\equiv L s_{i} \right\}. HenceM recognizes L.
(c) Suppose that L is regular and let k be the number of states in a DFA recognizing L. Then from part (a), L has index at most k. Conversely, if L has index k, then by part (b) it is recognized by a DFA with k states and thus is regular. To show that the index of L is the size of the smallest DFA accepting it, suppose that L’s index is exactly k. Then, by part (b), there is a k-state DFA accepting L. That is the smallest such DFA because if it were any smaller, then we could show by part (a) that the index of L is less than k.