GATE CS 2009 Q16 — Context-free Grammars and Push-down Automata

We analyze each statement to determine which one is FALSE:

• Statement A: "There is a unique minimal DFA for every regular language"
  True. According to the Myhill-Nerode theorem, for any regular language, there exists a unique minimal DFA (up to state renaming/isomorphism).
• Statement B: "Every NFA can be converted to an equivalent PDA."
  True. Every NFA recognizes a regular language. Since every regular language is also a context-free language, it can be accepted by a Pushdown Automaton (PDA) (by simply not using the stack).
• Statement C: "Complement of every context-free language is recursive."
  True. Every context-free language (CFL) is a recursive (decidable) language. Since recursive languages are closed under complementation, the complement of any CFL must also be a recursive language.
• Statement D: "Every nondeterministic PDA can be converted to an equivalent deterministic PDA."
  False. Nondeterministic PDAs (NPDAs) accept the class of Context-Free Languages (CFLs), while Deterministic PDAs (DPDAs) accept the class of Deterministic Context-Free Languages (DCFLs). Since DCFL is a proper subset of CFL (for example, the language $L = \{ww^R \mid w \in \{a,b\}^*\}$ is context-free but not deterministic context-free), not every NPDA can be converted to an equivalent DPDA.

Therefore, statement D is false.