44 votes 44 votes Which of the following is/are undecidable? $G$ is a CFG. Is $L(G) = \phi$? $G$ is a CFG. Is $L(G) = \Sigma^*$? $M$ is a Turing machine. Is $L(M)$ regular? $A$ is a DFA and $N$ is an NFA. Is $L(A) = L(N)$? $3$ only $3$ and $4$ only $1, 2$ and $3$ only $2$ and $3$ only Theory of Computation gatecse-2013 theory-of-computation decidability normal + – Arjun asked Sep 24, 2014 edited Jun 21, 2021 by Lakshman Bhaiya Arjun 11.0k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Kai commented Nov 19, 2016 reply Follow Share Regarding the option - Given a CFG. Is it empty or not? Since the Language is (<G>| G is a CFG and L(G) is empty). We can find one TM which accepts an empty string and one which doesn't. Then by Rice's theorem, this property is non trivial and thus undecidable for Recursively Enumerable languages which involve CFLs. What am I missing here? 2 votes 2 votes Kai commented Nov 26, 2016 reply Follow Share @Arjun Sir Can you give some intuition regarding why 2 is undecidable? 1 votes 1 votes yankur9 commented Feb 6, 2017 reply Follow Share link to pdf http://www.cs.nyu.edu/courses/fall09/V22.0453-001/chapter-4.pdf 1 votes 1 votes endurance1 commented Jan 14, 2021 reply Follow Share @Arjun sir, I couldn’t understand option C, is there any resource available ? 0 votes 0 votes Deepak Poonia commented Oct 27, 2022 reply Follow Share Find Video Solution Below: Detailed Video Solution 1 votes 1 votes Please log in or register to add a comment.
Best answer 35 votes 35 votes Correct Option: D First is Emptiness for CFG. Second is everything for CFG. Third is Regularity for REC Fourth is equivalence for regular. Gate Keeda answered Oct 10, 2014 edited May 6, 2021 by soujanyareddy13 Gate Keeda comment Share Follow See all 14 Comments See all 14 14 Comments reply Show 11 previous comments siddharths067 commented May 9, 2020 reply Follow Share Arent 1st , 2nd and 4th Decidable 3rd is undecidable why is answer d? 0 votes 0 votes Jamyang Louts commented Dec 6, 2020 reply Follow Share I think second option is equivalence problem. So, Equivalence for CFG is undecidable. 0 votes 0 votes JAINchiNMay commented Nov 24, 2022 reply Follow Share No @Jamyang Louts second problem is completeness problem , which is undecidable 2 votes 2 votes Please log in or register to add a comment.
10 votes 10 votes There is an algorithm to check whether the given CFG is empty, finite or infinite and also to convert NFA to DFA hence 1 and 4 are decidable Çșȇ ʛấẗẻ answered Dec 20, 2016 Çșȇ ʛấẗẻ comment Share Follow See all 0 reply Please log in or register to add a comment.