in Theory of Computation edited by
9,066 views
43 votes
43 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
in Theory of Computation edited by
by
9.1k views

4 Comments

1
1
@Arjun sir,

I couldn’t understand option C, is there any resource available ?
0
0

Find Video Solution Below:

Detailed Video Solution

1
1

2 Answers

34 votes
34 votes
Best answer

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

4 Comments

Arent 1st , 2nd and 4th Decidable

3rd is undecidable why is answer d?
0
0
I think second option is equivalence problem.

So, Equivalence for CFG is undecidable.
0
0

No @Jamyang Louts second problem is completeness problem , which is undecidable
 

0
0
9 votes
9 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