Which one of the following is FALSE?
2017
Which one of the following is FALSE?
- A.
There is a unique minimal DFA for every regular language
- B.
Every NFA can be converted to an equivalent PDA
- C.
Complement of every context-free language is recursive
- D.
Every non-deterministic PDA can be converted to an equivalent deterministic PDA
Attempted by 66 students.
Show answer & explanation
Correct answer: D
Option A is true because minimal DFAs are unique up to isomorphism for regular languages. Option B holds since regular languages recognized by NFAs are a subset of context-free languages recognized by PDAs. Option C is true because recursive languages are closed under complementation and contain all CFLs. However, Option D is false; non-deterministic PDAs are strictly more powerful than deterministic ones, and no general conversion exists. Therefore, Option D is the correct answer.