Let Lk $\{0,1\}$

$$

be the language defined as

Lk $=\{$xy $|$ x$,$ y in $\{0,1\}$

k

$,$ and the bitwise$-$AND of x and y is $0$

k

$\}.$

Observe that Lk is finite, and hence, regular. Prove that for all k$,$ any NFA that recognizes Lk has at least

$2$

k

states.