Multiple choice

Which of the following is/are undecidable?

  1. G is a CFG. Is L (G) = $\phi$?
  2. G is a CFG. IS L (G) = $\sum *$?
  3. M is a Turning 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
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

There is an algorithm to check whether the given CFG is empty, finite or infinite and also to convert NFA to DFA. Hence, 1 and 4 are decidable.

Keep practicing — related questions