GATE 2009
March 14, 2025
GATE 2009
March 14, 2025
GATE 2009
March 14, 2025
GATE 2009
March 14, 2025

GATE 2009

Question 16

Which one of the following is FALSE?

A
There is 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 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.
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.
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x