GATE 2013 CS (CS1) – Question 51
Which problems are undecidable? 1: Given CFG G, is L(G)=∅? 2: Given CFG G, is L(G)=Σ*? 3: Given TM M, is L(M) regular? 4: Given DFA A and NFA N, is L(A)=L(N)?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) 2 and 3
Explanation
CFG emptiness is decidable by marking generating nonterminals. CFG universality is undecidable. Whether a TM language is regular is a nontrivial semantic property, undecidable by Rice’s theorem. DFA/NFA equivalence is decidable after determinization and symmetric-difference emptiness testing. Thus 2 and 3, D.