GATE Computer Science (CS) 2016 Shift 1 Solved Paper
© examsiri.com
Question : 27 of 65
Marks:
+1,
-0
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) = Ï•?
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) = Ï•?
Go to Question: