Project ForgeWhich of the following decision problems are undecidable?
I. Given NFAs N1 and N2, is L(N1)∩L(N2)=Φ? II. Given a CFG G=(N,Σ,P,S) and a string x∈Σ*, does x∈L(G)? III. Given CFGs G1 and G2, is L(G1)=L(G2)? IV. Given a TM M, is L(M)=Φ?
- AI and IV only
- BII and III only
- III and IV only
- DII and IV only
Explanation
I: NFA-intersection emptiness is DECIDABLE (build the product automaton, check reachability of an accepting state). II: CFG membership is DECIDABLE (CYK/Earley parsing runs in finite time). III: CFG equivalence is UNDECIDABLE (a classical un-decidable problem for context-free languages). IV: TM language-emptiness is UNDECIDABLE (Rice's theorem, a non-trivial semantic property). So III and IV only.
Source: GATE CS 2016 (Session 1 / Set A) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.