Which of the following decision problems are undecidable?

Home » Theory of Computation » Theory of computation miscellaneous » Question

Which of the following decision problems are undecidable?
I. Given NFAs N₁ and N₂, is L(N₁) ∩ L(N₂) = Φ ?
II. Given a CFG G = (N, ∑ , P, S) and a string x ∈ ∑*, does x ∈ L(G) ?
III. Given CFGs G₁ and G₂ is L(G₁) = L(G₂)?
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

Correct Option: C

There is no known algorithm to verify whether the language accepted by TM is empty or not. Similarly there is no algorithm to verify whether language of CFG’s are equivalent.