1.

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

A. I and IV only
B. II and III only
C. III and IV only
D. II and IV only
Answer» D. II and IV only


Discussion

No Comment Found