Question

Let M be a finite automaton and let M' be obtained from M by interchanging the collections of accepting and non-accepting states.
Now consider the following statements:

I. If M is deterministic, then the language accepted by M' is the complement of the language accepted by M.

II. If M is Non-deterministic, then the language accepted by M' is the complement of the language accepted by M.

Which of the above is/are correct?

Answer 1

Option (a)

If M is deterministic, then the language accepted by M' is the complement of the language accepted by M.

If M is non-deterministic, then the language accepted by M' may not be the complement of the language accepted by M because NFA might have dead configurations.