Which one of the following is FALSE?
2017
Which one of the following is FALSE?
Answer: D. Every non-deterministic PDA can be converted to an equivalent deterministic PDA — 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…
- 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 199 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2