Which of the following decision problems are undecidable? I. Given NFAs…
2016
Which of the following decision problems are undecidable?
I. Given NFAs \(N_1\) and \(N_2\), is L(N1) ∩ L(N2) = ∅ ?
II. Given a CFG \(G = (N,Σ,P,S)\) and a string \(x ∈ Σ^∗\) , does \(x ∈ L(G)\)?
III. Given CFGs \(G_1\) and \(G_2\), is \(L(G_1) = L(G_2)\)?
IV. Given a TM \(M\), is \( L(M) = Φ\)?
- A.
I and IV only
- B.
II and III only
- C.
III and IV only
- D.
II and IV only
Attempted by 54 students.
Show answer & explanation
Correct answer: C
Answer: III and IV only
Why:
I. Emptiness of L(N1) ∩ L(N2) for NFAs is decidable. Construct the product NFA that recognizes the intersection and check whether any accepting state is reachable (graph reachability).
II. Membership of a string x in a context-free grammar G is decidable (for example by the CYK algorithm or other dynamic-programming parsing algorithms).
III. Equivalence of two CFGs is undecidable. If equality of CFG languages were decidable, then inclusion of one CFG language in another would be decidable too (test whether L(G1) ∪ L(G2) = L(G2)), but inclusion for CFGs is known to be undecidable.
IV. Emptiness of a Turing machine's language is undecidable. Reduce from the acceptance problem A_TM: given ⟨M,w⟩ build a machine M' that on any input ignores that input, simulates M on w, and accepts iff M accepts w. Then L(M') is empty exactly when M does not accept w, so deciding emptiness would decide A_TM, which is impossible.
A video solution is available for this question — log in and enroll to watch it.