Question

What is the complement of the language accepted by the NFA shown below? Assume ∑ = {a} and ε is the empty string.

(a) Φ

(b) ε

(c) a

(d) {a, ε}

This question was posed to me in a job interview.

My query is from Transformation from NFA to DFA in portion Finite Automata and Regular Expression of Compiler

Answer 1

The correct answer is (b) ε

The explanation is: The given alphabet ∑ contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’. Hence the complement is an empty string.