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

PYQ GATE 2016

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 143 students.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…