Question

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.

Lr = {u0v : u Є {0, 1}*, v € {0, 1}"−¹}.
student submitted image, transcription available below
(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 xl ≠ yl. Use x and y to give a contradiction with Lr = L(D).

Answer 1

To show that there has to be at least 2^r states in any DFA L_R, we can use proof by contradiction.

Step-by-step explanation:

To show that there has to be at least 2^r states in any DFA L_R, we can use proof by contradiction. Suppose we have a DFA D for L_R with less than 2^r states. We want to show that there are two different strings x and y in {0,1}^r that lead to the same state when run on D.

To do this, we can consider the largest index l such that xl and yl differ. Since xl and yl differ, there must be some substring u0v that is common to both xl and yl. This implies that the DFA D will reach the same state when run on x and y. Hence, we have a contradiction.