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}"−¹}.

(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 I be the largest index such that x # y. Use x and y to give a contradiction with L = L(D).

Answer 1

To show that any DFA L_R has to have at least 2^r states, we will proceed by contradiction. Suppose D is a DFA of 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 will reach the same state when D is run on them at the end.

Step-by-step explanation:

To show that any DFA L_R has to have at least 2^r states, we will proceed by contradiction. Suppose D is a DFA of 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 will reach the same state when D is run on them at the end.

Let x = 0^r and y = 1^r, both of length r, where 0^r represents a string of r zeros and 1^r represents a string of r ones. Since D has less than 2^r states, there must be some state that is reached after processing both strings. This means that D accepts both strings x0 = 0^r0 and y0 = 1^r0, where 0 is appended to the end of each string.

However, x0 and y0 differ at the last symbol, which contradicts the definition of L(D), since L(D) is defined as L(D) = {u0v : u ∈ {0, 1}*, v ∈ {0, 1}^(−1)}. Therefore, our assumption that D has less than 2^r states leads to a contradiction, and thus any DFA L_R must have at least 2^r states.