The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
3.6k 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.7k points)
edited by | 3.6k 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

+31 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.4k points)
edited by
0
what about option B ??
+3
we can definitely convert an nfa--->dfa--->dpda
0
Ignore this comment.
+11
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
0

Can anyone Please explain me, why @Bhagirathi explicitly mentioned in this question that " recursive languages are closed under complement". Is this statement have to do something with this question.

+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.7k 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.6k 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.7k points)
Answer:

Related questions



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

44,255 questions
49,747 answers
164,057 comments
65,844 users