which one of the following is FALSE? : GATE-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 non deterministic PDA can be converted to an equivalent deterministic



Explanation :

A)True.minimization of DFA always give minimal DFA. DFAs are how computer manipulate the regular expression. Size of DFA will determine space/time complexity.

B) Every regular language is CFL, so we can make PDA for regular language also.

C) True, CFL are not closed under complement.


Digvijay Pandey @digvijay
12 Nov 2015 08:41 pm
^^ CFLs not closed under complement so need to push up to CSL. Yes CSL are closed under complement so complement of CFL is CSL.

CSL is trivially recursive so complement of CFL must be recursive.

Abhishek Kumar Singh @abhish
13 Nov 2015 12:35 pm

NPDA is more powerful than DPDA  so option D is answer