9,066 views

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

@Arjun sir,

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

Find Video Solution Below:

Detailed Video Solution

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.

Arent 1st , 2nd and 4th Decidable

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

So, Equivalence for CFG is undecidable.

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

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
by