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

+28 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.1k points)
edited by
0
what about option B ??
+3
we can definitely convert an nfa--->dfa--->dpda
0
Ignore this comment.
+6
In option B, every NFA is already a PDA. Nothing to convert here.
+2
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.5k points)
+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 (7k points)
+4 votes
(d) Every non-deterministic PDA can be converted to an equivalent deterministic PDA
answered by
+1 vote
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 (8.1k 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

35,526 questions
42,802 answers
121,615 comments
42,165 users