The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2.3k 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 (69k points)
edited by | 2.3k views
NFA can be drawn for Regular languages and every regular is DCFL and for each DFCL ..PDA can be drawn ..Thus

NFA -> PDA

4 Answers

+25 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 Veteran (14.3k points)
selected by
what about option B ??
we can definitely convert an nfa--->dfa--->dpda
Ignore this comment.
In option B, every NFA is already a PDA. Nothing to convert here.
NFA can be drawn for Regular languages and every regular is DCFL and for each DFCL ..PDA can be drawn ..Thus

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

Ans is D.
answered by Loyal (4.7k points)
+4 votes
(d) Every non-deterministic PDA can be converted to an equivalent deterministic PDA
answered by anonymous
+4 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 Boss (7.8k 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

33,688 questions
40,231 answers
114,272 comments
38,803 users