edited by
11,018 views
44 votes
44 votes

Which of the following is/are undecidable?

  1. $G$ is a CFG. Is $L(G) = \phi$?
  2. $G$ is a CFG. Is $L(G) = \Sigma^*$?
  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
edited by

2 Answers

Best answer
35 votes
35 votes

Correct Option: D

  1. First is Emptiness for CFG.
  2. Second is everything for CFG.
  3. Third is Regularity for REC
  4. Fourth is equivalence for regular.
edited by
10 votes
10 votes
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
Answer:

Related questions