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

why second is undecidable pls explain?

---

@madhab we know that emptiness problem is decidable on cfl and we also know that CFL is not closed under complement operation so we cant say about its complement that is Σ*
parallely u can see that regular and dcfl are closed under complement and on regular and dcfl emptiness problem is decidable and also these are closed under complement so completeness problem is also decidable on regular an dcfl but not on cfl

---

@Arjun SIR,

What is this everything for CFG. ? Can u pls explain what is option B means ?

---

@gokou 

everything means E^*  according to him ; i think so.

L(G)=E^* ? this is decidable upto DCFL. not for rest wrt to chomsky hierarchy.

---

If i check that start symbol is "useful" for CFG, will this check emptiness of CFG ?

---

Please, some one explain to me why option B is undecidable because CFG is closed under emptiness? and Σ∗ is countable so simply it will be Decidable.

---

Third is Regularity for REC. Why is it REC and not RE asTM deals with RE and always halting TM deals with REC @Gate Keeda

---

Brij Mohan Gupta

in second option it is universality problem ,it is undecidable for cfl but decidable for dcfl.

---

 iarnav 

Regularity problem is undecidable for both REC & RE

---

thank you.

---

Can anyone explain why option 2 is undecidable and what does option 2 means?

---

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