GATE 2017 CS (CS2) – Question 51
L(R) is a regular-expression language, L(G) a context-free grammar language, L(M) a Turing-machine language. Which are undecidable? I: Given R,w, is w∈L(R)? II: Given G, is L(G)=∅? III: Given G, is L(G)=Σ*? IV: Given M,w, is w∈L(M)?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) III and IV only
Explanation
I is decidable by automaton simulation. II is decidable by marking productive grammar symbols and checking the start symbol. III is the undecidable CFG universality problem. IV is the undecidable Turing-machine acceptance problem. Thus precisely III and IV, D.