##### 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

PDA.

**Answer**

ANSWER : D

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.

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

NPDA is more powerful than DPDA so option D is answer

## Pages