Question

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

1. I and IV only
2. II and III only
3. III and IV only
4. II and IV only

Answer 1

Correct Answer - Option 3 : III and IV only

I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = ϕ?

This is decidable, when we convert the NFA into DFA, if no common final state in it. Then this will become true.

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

Membership property of a context free grammar is decidable.

III. Given CFGs G1 and G2, is L(G1) = L(G2)?

Equivalence of two context free grammar is undecidable.

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

Emptiness problem of Turing machine is undecidable.