For every integer k $1,$ let Lk $=\{$ w $\{0,1\}*||$w$|$ k and the kth

bit of w from the end is $1\}.$

a$.$Give an NFA with k$+1$ states that accepts the language Lk$.$

b$.$Let A$=($Q$,\{0,1\},,$ q$0,$ F$)$ be any DFA that accepts Lk$.$ Prove that if x$,$ y are

two different binary strings of length k$,$ then $($q$0,$x$)!=($q$0,$y$).$

$($Hint: Suppose that x$,$ y differ in the i$-$th bit, and consider the strings x$0$i$-1$ and y$0$i$-1.$ Are

these strings in Lk$?$ Should the DFA end up in the same state after processing each of

these strings?$)$

c$.$ Prove that every DFA that accepts Lk must have at least $2$k states.