Suppose r is positive and the t-th symbol from the right end is a 0. We just want to show in this whole exercise that Any DFA L_R there has to be at least 2^r states.

(a) For contradiction, suppose that D is a DFA of L_r with less than 2^r states. Show that there are two different strings x,y in {0,1}^r such that running D on X reach the same state as running D on y at the end

(b) Given that x and y are different, let l be the largest index such that x_l y_l. Use x and y to give a contradiction with L_r = L(D).

Lr={u0v:u{0,1},v{0,1}r1}