Question

Which of the following is FALSE?

• A. Every NFA can be converted to an equivalent PDA
• B. Complement of every context free language is recursive
• C. There is a unique minimal DFA for every regular language
• D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA

Hint:

Nondeterministic PDAs and deterministic PDAs have different expressive powers. Not all nondeterministic PDAs can be converted into deterministic ones.

Answer 1

The Correct Option is D

It is FALSE that every nondeterministic PDA (NPDA) can be converted into an equivalent deterministic PDA (DPDA). The class of languages recognized by a DPDA is strictly smaller than that recognized by an NPDA. In contrast, all the other statements are true: every NFA can be converted to a PDA, the complement of every context-free language is recursive, and there is a unique minimal DFA for every regular language.