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.

edited | 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

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
0
+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.
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
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)
(d) Every non-deterministic PDA can be converted to an equivalent deterministic PDA
by
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
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)

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