GATE CS 2012 Q12 — Regular Expressions and Finite Automata

What is the complement of the language accepted by the NFA shown below?
Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.

View worked solution

Answer: B

To find the complement of the language accepted by the given NFA, we first determine the language $L$ accepted by it.

The NFA starts at the initial state and requires at least one transition on symbol $a$ to reach an accepting state.
Once in the accepting state, any number of additional $a$ 's can be read.
Therefore, the language accepted by the NFA is: $L = a^+ = \{a, aa, aaa, \dots\}$

The alphabet is given as $\Sigma = \{a\}$ . The set of all possible strings over this alphabet is:

\Sigma^* = \{a\}^* = \{\epsilon, a, aa, aaa, \dots\}

The complement of the language $L$ (denoted as $\overline{L}$ ) is defined as:

\overline{L} = \Sigma^* \setminus L

\overline{L} = \{\epsilon, a, aa, aaa, \dots\} \setminus \{a, aa, aaa, \dots\}

\overline{L} = \{\epsilon\}

Thus, the complement of the language accepted by the NFA is $\{\epsilon\}$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Related questions