Suppose r is positive and the t-th symbol from the right end is a 0 . We just want to show in this whol exercise that Any DFA L_R there has to be at least 2r states. Lr={u0v:u{0,1},v{0,1}r1} (a) For contradiction, suppose that D is a DFA of Lr with less than 2r 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 (b) Given that x and y are different, let I be the largest index such that x=y. Use x and y to give a contradiction with Lr=L(D)