Which one of the following is FALSE?
2009
Which one of the following is FALSE?
- A.
There is 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 nondeterministic PDA can be converted to an equivalent deterministic PDA.
Attempted by 25 students.
Show answer & explanation
Correct answer: D
Answer: The false statement is: "Every nondeterministic PDA can be converted to an equivalent deterministic PDA."
Reason: Nondeterministic pushdown automata (NPDAs) accept all context-free languages, while deterministic pushdown automata (DPDAs) accept only deterministic context-free languages (DCFLs). The class of DCFLs is a strict subset of the class of CFLs, so there exist context-free languages that no deterministic PDA can recognize. Hence conversion from an arbitrary NPDA to an equivalent DPDA is not always possible.
Minimal DFA: For any regular language, minimization yields a canonical minimal DFA unique up to renaming of states (isomorphism).
NFA to PDA: Any NFA can be simulated by a PDA by not using the stack, so every NFA has an equivalent PDA.
Complement of CFL: Every context-free language is decidable (e.g., membership can be decided with algorithms like CYK), so the complement of a context-free language is decidable (recursive).
Correct final statement: The claim that every nondeterministic PDA has an equivalent deterministic PDA is false because deterministic PDAs recognize strictly fewer languages than nondeterministic PDAs.
A video solution is available for this question — log in and enroll to watch it.