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

+33 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.
+12
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.8k 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 Boss (10.1k 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
47,881 questions
52,231 answers
182,124 comments
67,651 users