Question 12

Let us trace the given NFA (states named $q_0$, $q_1$, $q_2$ from left to right):

• Start state is $q_0$.
• There is a transition $q_0 \xrightarrow{a} q_1$.
• State $q_1$ is the only accepting (double circle) state.
• There is an $\varepsilon$-transition $q_1 \xrightarrow{\varepsilon} q_2$.
• There is a backward $\varepsilon$-transition $q_2 \xrightarrow{\varepsilon} q_0$.

1. Language accepted by the NFA:

   • To reach the accepting state $q_1$ from $q_0$, a path must consume at least one '$a$' via $q_0 \xrightarrow{a} q_1$.
   • Because $q_0$ is not an accepting state and the only way to reach $q_1$ is by reading an '$a$', the empty string $\varepsilon$ is not accepted.
   • From $q_1$ the automaton can return to $q_0$ via $q_1 \xrightarrow{\varepsilon} q_2 \xrightarrow{\varepsilon} q_0$, allowing another '$a$' to be consumed.
   • Thus, any string containing one or more '$a$'s is accepted:
     $$L = \{a, aa, aaa, \dots\} = a^+$$

2. Complement of $L$:
   The alphabet is $\Sigma = \{a\}$. The universal language is $\Sigma^* = a^*$.
   The complement of $L$ is:

   $$\overline{L} = \Sigma^* - L = a^* - a^+ = \{\varepsilon\}$$

This matches option (B).