Project ForgeTheory of Computation
Finite Automata & Regular Languages
GATE 2012
Hard
What is the complement of the language accepted by the NFA shown below? Assume Σ = {a} and ε is the empty string.
The NFA has states q0 (start) → q1 (accepting, double-circled) on input 'a'; q1 → q2 on ε; and q2 → q0 on ε (looping back to the start).
- A∅
- {ε}
- Ca*
- D{a, ε}
Explanation
Starting at q0, reading one 'a' reaches the accepting state q1 — and from q1, ε-moves back through q2 to q0 allow reading more a's and reaching q1 again. So the accepted language is L = a⁺ = {a, aa, aaa, …}. Since a* = {ε} ∪ a⁺, the complement of L within a* is exactly {ε}.
Source: GATE CS 2012 (2012)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.