GATE CSE 2013 | Question: 41

Question

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)$?

• A. $3$ only      
• B. $3$ and $4$ only      
• C. $1, 2$ and $3$ only      
• D. $2$ and $3$ only

Comments

link to pdf

http://www.cs.nyu.edu/courses/fall09/V22.0453-001/chapter-4.pdf

---

@Arjun sir,

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

---

Find Video Solution Below:

Detailed Video Solution

Answer 1

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.

Comments

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
 

Answer 2

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