The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
3.4k views

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.

asked in Theory of Computation by Veteran (59.6k points)
edited by | 3.4k views
+1
NFA can be drawn for Regular languages and every regular is DCFL and for each DFCL ..PDA can be drawn ..Thus

NFA -> PDA

5 Answers

+30 votes
Best answer

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.

answered by Boss (14.3k points)
edited by
0
what about option B ??
+3
we can definitely convert an nfa--->dfa--->dpda
0
Ignore this comment.
+8
In option B, every NFA is already a PDA. Nothing to convert here.
+3
NFA can be drawn for Regular languages and every regular is DCFL and for each DFCL ..PDA can be drawn ..Thus

NFA -> PDA
+8 votes
The Power of NPDA is greater than DPDA, hence we cannot convert NPDA into an equivalent DPDA.

Ans is D.
answered by Active (4.6k points)
0
Can we say that

if a cfl is subset of rec enimurable so its complement is also rec enumurable
+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

answered by Loyal (7.4k points)
+4 votes
(d) Every non-deterministic PDA can be converted to an equivalent deterministic PDA
answered by
+2 votes
Deterministic PDA cannot handle languages or grammars with ambiguity.

nondeterministic can handle languages with ambiguity and any context-free grammar.

Therefore,  every nondeterministic PDA cannot be converted to an equivalent deterministic PDA.
answered by Loyal (9.6k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,993 questions
47,622 answers
146,898 comments
62,346 users