This is a question from GATE CSE 2009.

Which 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.

The answer provided to me (without any explanation) is B, which I think is wrong.

Here is my approach.

A] Every RL has an equivalent DFA and there is one unique minimal DFA for a given RL. [so True]

B] Since RL are proper sub-set of CFL and every RL has equivalent FA and every CFL has equivalent PDA, every FA can be converted to PDA but not vice versa. [so True]

C] Given a CFL we can create an equivalent Total TM [RECURSIVE], RECURSIVE languages are closed under complement. [so True]

D] This is only remaining option and by method of elimination answer.

Is my answer correct?


A is true, but I don't find your argument convincing (it simply restates the claim). See this question for example.

B is not the correct answer to this problem, because as you say it's true. Your reasoning isn't very formal though, and swaps some reduction orders. A correct reduction would be NFA → (superset construction)→ DFA → (trivial) → PDA.

C seems fine to me.

D is indeed left over, and is indeed false. Inherently ambiguous context-free languages can be recognized by nondeterministic PDAs, but not by deterministic PDAs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.