Question written under $[$solve$]-1\mathrm{.}35.$

$1\mathrm{.}34$ Let x and y be strings and let L be any language. We say that x and y are distinguishable by L if some string z exists whereby exactly one of the strings xz and yz is a member of L; otherwise, for every string z$,$ xz in L whenever yz in L and we say that x and y are indistinguishable by L$.$ If x and y are indistinguishable by L we write x $=$L y$.$ Show that $=$L is an equivalence relation.

$1\mathrm{.}35$ Read problem $1\mathrm{.}34.$ 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. Morever, its index is the size of the smallest DFA recognizing it$.$

$[$Solve:$]$

We ignore the X in the text version; it is easy to see that the index for an arbitrary X is always less than for W$,$ the set of all words. So we stick with that.

The index of L is defined as the maximum number $($possibly infinite$)$ of any subset D $$ W in which no two members are distinguishable. Another way to say this is that the index is the number of equivalence classes for $$L$.$ Prove that if L is recognized by a DFA with k in N states, then the index of L is $$ k$.$

Hint: Suppose that x and y are two words which end in the same state q$.$ Show that x $$L y$.$

Feel free to solve b$.$ and c$.$ of $1\mathrm{.}35$ as well.