Claim 2: If two states are distinguishable, then they are distin- guishable by a string of length at most n. One way to prove this is to look closely at the successive refinement al- gorithm discussed in the notes on minimizing finite state machines. Recall that in the successive refinement algorithm when the algorithm splits a class C into two classes C and C- C', it learns that every state in C is distin- guishable from every state in C-C'. 3a. Explain how the algorithm can be extended so that when a class C splits into C' and C - C', for every pair of states (41, 42) where qi goes into C", and 42 goes into C - C', the algorithm can quickly determine and record a string w(1,2) that distinguishes qi from 42. Here the word "quickly" rules out trying out different strings to find one that distinguishes qi and q2. Rather, the algorithm has a simple rule that creates w(1,2) at that point. 3b. Explain how the length of w(1,2) relates to the lengths of distin- guishing strings already determined by the algorithm. 3c. Abstractly, suppose you have two sets with a total of n elements, and you pick one set that has more than one element, and split it into two sets in some way. At that point you have three sets. If there is a set with more than one element, pick one such set, and split it into two sets in some way. Continue in this way until no set has more than one element. How many splits will be executed in this process? Explain. 3d. Use your answers and insights from problems 3a, 3b, 3c, to create a proof of Claim 2. Claim 2: If two states are distinguishable, then they are distin- guishable by a string of length at most n. One way to prove this is to look closely at the successive refinement al- gorithm discussed in the notes on minimizing finite state machines. Recall that in the successive refinement algorithm when the algorithm splits a class C into two classes C and C- C', it learns that every state in C is distin- guishable from every state in C-C'. 3a. Explain how the algorithm can be extended so that when a class C splits into C' and C - C', for every pair of states (41, 42) where qi goes into C", and 42 goes into C - C', the algorithm can quickly determine and record a string w(1,2) that distinguishes qi from 42. Here the word "quickly" rules out trying out different strings to find one that distinguishes qi and q2. Rather, the algorithm has a simple rule that creates w(1,2) at that point. 3b. Explain how the length of w(1,2) relates to the lengths of distin- guishing strings already determined by the algorithm. 3c. Abstractly, suppose you have two sets with a total of n elements, and you pick one set that has more than one element, and split it into two sets in some way. At that point you have three sets. If there is a set with more than one element, pick one such set, and split it into two sets in some way. Continue in this way until no set has more than one element. How many splits will be executed in this process? Explain. 3d. Use your answers and insights from problems 3a, 3b, 3c, to create a proof of Claim 2