What is the complement of the language accepted by the NFA shown below? Assume…
2012
What is the complement of the language accepted by the NFA shown below? Assume \(\sum = \{a\}\) and \(\varepsilon\) is the empty string
- A.
\(\phi\) - B.
\(\{\varepsilon \}\) - C.
\(a^*\) - D.
\(\{a, \varepsilon \}\)
Attempted by 202 students.
Show answer & explanation
Correct answer: B
Key insight: the NFA accepts every non-empty string of a's, so its complement over Σ = {a} is {ε}.
ε is not accepted because the start state is not accepting and there is no ε-path from the start to an accepting state.
The string "a" is accepted by taking the a-transition from the start to the accepting state.
After reaching the accepting state, ε-transitions allow returning to the start, so any positive number of a's (a+, i.e. a, aa, aaa, ...) is accepted.
Conclusion: The language accepted by the NFA is a+ (all non-empty strings of a's), so its complement over Σ = {a} is {ε}.