$1\mathrm{.}64$ Let $N$ be an NFA with $k$ states that recognizes some language $A.$

a$.$ Show that if $A$ is nonempty, A contains some string of length at most $k.$

b$.$ Show, by giving an example, that part $($a$)$ is not necessarily true if you replace

both $A\text{'}$s by $\frac{?}{\text{b}\text{a}\text{r}}(A).$

c$.$ Show that if $\frac{?}{\text{b}\text{a}\text{r}}(A)$ is nonempty, $\frac{?}{\text{b}\text{a}\text{r}}(A)$ contains some string of length at most $2^k.$

d$.$ Show that the bound given in part $($c$)$ is nearly tight; that is$,$ for each $k,$

demonstrate an NFA recognizing a language $A_k$ where $\frac{?}{\text{b}\text{a}\text{r}}(A_k)$ is nonempty and

where $\frac{?}{\text{b}\text{a}\text{r}}(A_k),$s shortest member strings are of length exponential in $k.$ Come as

close to the bound in $($c$)$ as you can.