Problem $15($Homework $2$ Problem $2).$ Let $L_k$sube$\{0,1{\}}^{**}$ be the language defined as $|),(yin\{0,1{\}}^k,$ and the bitwise$-$AND of $x$ and $y$ is $\{$:$0^k\}.$

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