29 votes 29 votes Which of the following statements is false? The Halting Problem of Turing machines is undecidable Determining whether a context-free grammar is ambiguous is undecidable Given two arbitrary context-free grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$ Given two regular grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$ Theory of Computation gate1996 theory-of-computation decidability easy + – Kathleen asked Oct 9, 2014 edited Feb 5, 2018 by kenzou Kathleen 8.0k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply smsubham commented Dec 23, 2019 reply Follow Share https://gatecse.in/grammar-decidable-and-undecidable-problems/ 1 votes 1 votes val_pro20 commented Feb 2, 2021 reply Follow Share option c is decidable for Deterministic context free grammar 0 votes 0 votes Deepak Poonia commented Oct 27, 2022 reply Follow Share Click for Video Solution 0 votes 0 votes Please log in or register to add a comment.
Best answer 33 votes 33 votes Answer is D. Equivalence of Regular languages is decidable. Membership, Emptiness, Finiteness, Equivalence, Ambiguity, Regularity, Everything, Disjointedness... All are decidable for Regular languages. First $3$ for CFL. Only $1$st for CSL and REC. None for RE. Gate Keeda answered Oct 10, 2014 edited Jun 15, 2018 by Milicevic3306 Gate Keeda comment Share Follow See all 3 Comments See all 3 3 Comments reply Arjun commented Oct 10, 2014 reply Follow Share http://gatecse.in/wiki/Grammar:_Decidable_and_Undecidable_Problems 11 votes 11 votes Shiva Sagar Rao commented Feb 2, 2021 reply Follow Share Updated link: https://gatecse.in/grammar-decidable-and-undecidable-problems/ 1 votes 1 votes CheeseCuBES commented Feb 8, 2021 reply Follow Share But if w is a member of a TM is undecidable. Isnt that the halting problem? 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes A) halting problem of turing machine are undecidable. B) Ambiguty problem of CFG are undecidable C) equvalance problem of CFG is undecidable d) equvalance problem of regular grammar is decidable so option d is correct option abhishekmehta4u answered Mar 28, 2019 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.