3.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 | 3.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.

edited
0
+3
we can definitely convert an nfa--->dfa--->dpda
0
Ignore this comment.
+11
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.

The Power of NPDA is greater than DPDA, hence we cannot convert NPDA into an equivalent DPDA.

Ans is D.
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

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

1
2