Which of the following is/are undecidable? 1. G is a CFG.

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

Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = Φ ?
2. G is a CFG. Is L(G) = ∑* ?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?

1. 3 only
2. 3 and 4 only
3. 1, 2 and 3 only
4. 2 and 3 only

Correct Option: D

1. G is a CFG. Is L(G) = φ ?
Decidable
2. G is a CFG. Is L(G) = S * ?
Undecidable
3. M is a Turing Machine. Is L (M) regular ?
Undecidable.
4. A is a DFA and N is an NFA. Is L(A) = L(N) ?
Decidable.
Hence, the correct answer is (d) 2 and 3 only.