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.
Subscribe
Login
0 Comments