GATE 2009
March 14, 2025GATE 2009
March 14, 2025GATE 2009
|
Question 16
|
Which one of the following is FALSE?
|
There is unique minimal DFA for every regular language.
|
|
|
Every NFA can be converted to an equivalent PDA.
|
|
|
Complement of every context-free language is recursive.
|
|
|
Every non-deterministic PDA can be converted to an equivalent deterministic PDA.
|
Question 16 Explanation:
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 = {wwr | w ϵ {a,b}*} is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.
L = {wwr | w ϵ {a,b}*} is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.
Correct Answer: D
Question 16 Explanation:
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 = {wwr | w ϵ {a,b}*} is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.
L = {wwr | w ϵ {a,b}*} is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.