0 votes 0 votes Which of the following statements are NOT true? Given two regular grammars $G1$ and $G2$, it is undecidable whether $L (G1) = L (G2)$. Given two arbitrary context-free grammars $G1$ and $G2$, it is undecidable whether $L (G1) = L(G2)$. All recursive enumerable languages would be recursive, if halting problem is decidable. For any CFG, it is undecidable whether or not a particular non-terminal "X" in G is reachable. I,IV and II II and IV I and IV I,II and III Theory of Computation tbb-toc-2 theory-of-computation decidability + – Bikram asked Aug 12, 2017 retagged Sep 17, 2020 by ajaysoni1924 Bikram 411 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Manu Thakur commented Sep 8, 2017 reply Follow Share (iii) All recursive enumerable languages would be recursive, if halting problem is decidable. this statement is correct then how can (C) be correct option? 1 votes 1 votes joshi_nitish commented Sep 8, 2017 reply Follow Share yes, only (i) and (iv) are false. 1 votes 1 votes sourav. commented Jan 3, 2018 reply Follow Share @joshi i too think (iii) is absolutely correct .. i had no option left so i went for option c) 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes it's screenshot of peter linz so statement 3 is true BASANT KUMAR answered Aug 7, 2018 selected Aug 18, 2019 by Bikram BASANT KUMAR comment Share Follow See all 2 Comments See all 2 2 Comments reply KUSHAGRA गुप्ता commented Sep 1, 2019 reply Follow Share @Bikram Sir, In the answer key it is still showing C as answer. I think that you have to edit the options. 1 votes 1 votes Akanksha Agrawal commented Nov 8, 2019 reply Follow Share @Bikram sir here in stmt 2 it is given that for 2 arbitrary CFG G1 and G2 is L(G1)=L(G2) i.e equality problem of cfl if both arbitrary choosen grammar G1 and G2 are DCFG then in that weather L(G1)=L(G2) is decidable(equality problem of DCFL is decidable ) and in this case statement 2 is false so correct answer should be B. sir, is am I correct ? 0 votes 0 votes Please log in or register to add a comment.