Let N be an NFA with k states that recognizes

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’s by A̅.

c. Show that if A̅ is nonempty, A̅ contains some string of length at most 2k.

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 A̅_k is nonempty and where A̅_k’s shortest member strings are of length exponential in k. Come as close to the bound in (c) as you can.