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 Φ ???

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

Sir I didn't get the 1st part soln plz elaborate y it is so ?

 

Thanks

---

in this question in option 3 are we talking about CFL or DCFL?????

---

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

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