Which 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) = ϕ?

Question

Examsnet · Accepted Answer

Correct Answer is : III and IV only

GATE Computer Science (CS) 2016 Shift 1 Solved Paper