32 votes 32 votes Which of the following decision problems are undecidable? Given NFAs $N_1$ and $N_2$ , is $L(N_1) \cap L(N_2) = \Phi$ Given a CFG $G = (N,\Sigma,P,S)$ and a string $x \in \Sigma^{*}$, does $x \in L(G)$} ? Given CFGs $G_1$ and $G_2$, is $L (G_1) = L(G_2)$? Given a TM $M$, is $L(M)=\Phi$ ? I and IV only II and III only III and IV only II and IV only Theory of Computation gatecse-2016-set1 theory-of-computation decidability easy + – Sandeep Singh asked Feb 12, 2016 edited Feb 5, 2018 by kenzou Sandeep Singh 8.5k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Miny commented Feb 16, 2017 reply Follow Share I am confused on equivalence of cfg. We can draw two pda and compare the pda right? 0 votes 0 votes daksirp commented Jul 9, 2018 reply Follow Share can anyone explain option IV ?? does it mean - Language accepted by TM M doesnt accept anything i,e Φ ??? 0 votes 0 votes Please log in or register to add a comment.
Best answer 63 votes 63 votes 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. Membership in CFG is Decidable (CYK algorithm) Equivalence of Two context free grammars is Undecidable. For TM M , $L(M) = \phi $ is Undecidable. Correct Answer: $C$ Praveen Saini answered Feb 12, 2016 edited May 9, 2019 by Naveen Kumar 3 Praveen Saini comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Ravi8770071203 commented Sep 11, 2021 reply Follow Share Sir I didn't get the 1st part soln plz elaborate y it is so ? Thanks 0 votes 0 votes Ankit Meena commented Jun 21, 2022 reply Follow Share in this question in option 3 are we talking about CFL or DCFL????? 0 votes 0 votes Abhrajyoti00 commented Oct 18, 2022 reply Follow Share @Ankit Meena We are talking about language produced by CFG, by default CFL (because DCFL is also CFL). For CFL, equivalence is undecidable. 0 votes 0 votes Please log in or register to add a comment.
10 votes 10 votes 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 Paras Nath answered Sep 24, 2016 edited Jan 13, 2018 by Puja Mishra Paras Nath comment Share Follow See all 0 reply Please log in or register to add a comment.
7 votes 7 votes C is the answer Gagan answered Feb 12, 2016 Gagan comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes C Is Correct 2nd is Basic Rule We Can not Compare two CFG are Equal or Not 4th is we Not Say That chalam121 answered Mar 26, 2018 chalam121 comment Share Follow See 1 comment See all 1 1 comment reply abhishekmehta4u commented Mar 26, 2018 reply Follow Share 4th one is emptiness problem of turing machine which is undecidable 0 votes 0 votes Please log in or register to add a comment.