retagged by
15,539 views
45 votes
45 votes

Which one of the following is FALSE?

  1. There is a unique minimal DFA for every regular language

  2. Every NFA can be converted to an equivalent PDA.

  3. Complement of every context-free language is recursive.

  4. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

retagged by

6 Answers

Best answer
54 votes
54 votes

Correct Option: D

NDPA is more powerful than DPDA, so they are not equivalent. Actually, DPDA is a proper subset of NDPA.

C is TRUE as CFL is a proper subset of recursive languages and recursive languages are closed under complement.

edited by
8 votes
8 votes
The Power of NPDA is greater than DPDA, hence we cannot convert NPDA into an equivalent DPDA.

Ans is D.
6 votes
6 votes
  1. There is a unique minimal DFA for every regular language       T

  2. Every NFA can be converted to an equivalent PDA.                 T

  3. Complement of every context-free language is recursive.           T

  4. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.           F

4 votes
4 votes
(d) Every non-deterministic PDA can be converted to an equivalent deterministic PDA
Answer:

Related questions

25 votes
25 votes
6 answers
1
Kathleen asked Sep 22, 2014
7,956 views
$(1217)_8$ is equivalent to$(1217)_{16}$$(028F)_{16}$$(2297)_{10}$$(0B17)_{16}$
34 votes
34 votes
7 answers
2
Kathleen asked Sep 22, 2014
20,200 views
$$S \to aSa \mid bSb\mid a\mid b$$The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of:all palindromesall odd length palindromesstrings t...
46 votes
46 votes
7 answers
4
Kathleen asked Sep 22, 2014
20,943 views
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$.end with $0$.end with $00$.contain the substring $00$.