GATE CSE 2016 | Set 1 | Question: 17

Question

Which of the following decision problems are undecidable?

1. Given NFAs $N_1$ and $N_2$ , is $L(N_1) \cap L(N_2) = \Phi$
2. Given a CFG $G = (N,\Sigma,P,S)$ and a string  $x \in \Sigma^{*}$, does  $x \in L(G)$} ?
3. Given CFGs  $G_1$ and $G_2$, is $L (G_1) = L(G_2)$?
4. Given a TM $M$, is $L(M)=\Phi$ ?

• A. I and IV only
• B. II and III only 
• C. III and IV only
• D. II and IV only

Comments

I am confused on equivalence of cfg. We can draw two pda and compare the pda right?

---

can anyone explain option IV ??

does it mean - Language accepted by TM M doesnt accept anything i,e Φ ???

---

@daksirp it's emptyness problem of Turing maching or RE language. which is undecidable

Answer 1

1. is Decidable, we may use cross product of NFA (or by converting them into DFA) , if We didn't get final states of both together at any state in it. then $L(N_1)\cap L(N_2)= \phi$ , Disjoint languages.
2. Membership in CFG is Decidable (CYK algorithm)
3. Equivalence of Two context free grammars is Undecidable.
4. For TM M , $L(M) = \phi $ is Undecidable.

Correct Answer: $C$

Comments

@Ankit Meena We are talking about language produced by CFG, by default CFL (because DCFL is also CFL). For CFL, equivalence is undecidable.

---

cant we see if none of the states in the TM go to accepting state then it will be empty lang ? isn't this algo correct ?

---

@Rana-G it can be possible that u can't able to reach final state means ur TM is never halting.

Answer 2

Option C will be right option 

Explanation::
Since equality problem is always undecidable in the case of CFL,CSL,RL and RE.

Similarly Emptiness proble is Undecidable in the case of TM,CSL,RL

Answer 3

C is the answer

Answer 4

C Is Correct

2nd is Basic Rule We Can not  Compare two CFG are Equal or Not

4th is we Not Say That

Comments

4th one is emptiness problem of turing machine which is undecidable

Answer 5

Check this. It might help..