$5.[12$ points$]$ Let r be a positive integer and Lr be the following language over $\{0,1\}$: Lr $=$ u$0$v : u in $\{0,1\},$v in $\{0,1\}$r$1.$

Equivalently, a string is in Lr if and only if its r$-$th symbol from the right end is $0.$ In this problem we show that any DFA for Lr must have at least $2$r states:

$($a$)[6$ points$]$ Assume for a contradiction that D is a DFA for Lr 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 reaches the same state as running D on y at the end.

$($b$)[6$ points$]$ Continue from $($a$).$ 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$).($Hint: Consider the following two strings x $0$l$1$ and y $0$l$1.)$