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

Regarding the option - Given a CFG. Is it empty or not?

Since the Language is (<G>| G is a CFG and L(G) is empty). We can find one TM which accepts an empty string and one which doesn't. Then by Rice's theorem, this property is non trivial and thus undecidable for Recursively Enumerable languages which involve CFLs.
What am I missing here?

---

@Arjun Sir

Can you give some intuition regarding why 2 is undecidable?

---

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