Which of the following decision problems are undecidable? I. Given NFAs…

GATE · 2016 · CS · Set 1 · Computer Science & IT

Which of the following decision problems are undecidable?

I. Given NFAs N1N_1 and N2N_2, is L(N1​) ∩ L(N2​) = ∅ ?

II. Given a CFG G=(N,Σ,P,S)G = (N,Σ,P,S) and a string x∈Σ∗x ∈ Σ^∗ , does x∈L(G)x ∈ L(G)?

III. Given CFGs G1G_1 and G2G_2, is L(G1)=L(G2)L(G_1) = L(G_2)?

IV. Given a TM MM, is L(M)=Φ L(M) = Φ?

  1. A.

    I and IV only

  2. B.

    II and III only

  3. C.

    III and IV only

  4. D.

    II and IV only

Attempted by 110 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…