The Gateway to Computer Science Excellence
+32 votes
4.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.

in Theory of Computation by Veteran (52.2k points)
edited by | 4.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

7 Answers

+38 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.

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.
+17
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.

0
What about option a? Nfa can't be converted to pda, as pda is finite automata + a stack.
+8 votes
The Power of NPDA is greater than DPDA, hence we cannot convert NPDA into an equivalent DPDA.

Ans is D.
by Active (4.4k 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

by Loyal (7.3k points)
+4 votes
(d) Every non-deterministic PDA can be converted to an equivalent deterministic PDA
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.
by Boss (10.8k points)
0 votes
As we know there are several languages (CFL) for which we only have NPDA, i.e. these languages cannot be recognized by DPDA. For example
L= {$w^{}$$w^{r}$ | w ϵ {a,b}* } is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.
by Active (1.2k points)
0 votes

Expressive Power::: FA< Deterministic PDA < Non-Deterministic PDA <LBA < TM

A. There is a unique minimal DFA for every regular language is TRUE.

B. Every NFA can be converted to an equivalent PDA is TRUE because PDA is more powerful than NFA

C. Complement of every context-free language is recursive. is TRUE.

D. Every non-deterministic PDA can be converted to an equivalent deterministic PDA. is FALSE because NPDA is more powerful than DPDA. E.g. L= {ww^r | w ϵ {a,b}* } is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA

 

by Junior (529 points)
edited by
Answer:
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
50,737 questions
57,385 answers
198,557 comments
105,369 users