GATE CSE 2009 | Question: 16, ISRO2017-12

Question

Which one of the following is FALSE?

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

• B. Every NFA can be converted to an equivalent PDA.

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

• D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Comments

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 is wrong that's why option D is right

---

😂 Fact though

Answer 1

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

Comments

@Dhiraj Raj 

We know that CFL’s are subset of Recursive Languages, ie every CFL is also a Recursive Language. 

Now one of the properties of Recursive Languages is that Complement of a Recursive Language is also Recursive, more formally Recursive Languages are closed under complementation. Hence complement of every CFL would always be Recursive.

---

CFL itself may not remain CFL after complement as CFL is not closed under complement but since its recursive and that is closed under complement hence C is true. Is that right???

---

NFA alwayas converted pda you can think like this,NFA converted to DFA then DFA to PDA then we can say that NFA are converted to PDA

Answer 2

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

Ans is D.

Comments

Can we say that

if a cfl is subset of rec enimurable so its complement is also rec enumurable

---

Yes, actually CFL is subset of recursive language(REC). Also recursive language is subset of recursive enumerable(RE) language. Although RE not closed under complementation but REC are closed under complementation. CFL are subset of REC so compelement of CFL is REC. As REC are subset of RE so complement of CFL is RE also.

Answer 3

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

Answer 4

(d) Every non-deterministic PDA can be converted to an equivalent deterministic PDA

Answer 5

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.

Comments

https://gateoverflow.in/6370/complement-contet-language-recursive-recursive-enumerable

Answer 6

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.