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 Show 2 previous comments 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 Madhab commented Jul 23, 2016 reply Follow Share why second is undecidable pls explain? 2 votes 2 votes saurabh rai commented Oct 22, 2016 reply Follow Share @madhab we know that emptiness problem is decidable on cfl and we also know that CFL is not closed under complement operation so we cant say about its complement that is Σ* parallely u can see that regular and dcfl are closed under complement and on regular and dcfl emptiness problem is decidable and also these are closed under complement so completeness problem is also decidable on regular an dcfl but not on cfl 23 votes 23 votes PEKKA commented Dec 5, 2016 reply Follow Share @Arjun SIR, What is this everything for CFG. ? Can u pls explain what is option B means ? 1 votes 1 votes Rajesh Pradhan commented Dec 8, 2016 reply Follow Share @gokou everything means E* according to him ; i think so. L(G)=E* ? this is decidable upto DCFL. not for rest wrt to chomsky hierarchy. 1 votes 1 votes Sachin Mittal 1 commented Jan 23, 2017 reply Follow Share If i check that start symbol is "useful" for CFG, will this check emptiness of CFG ? 5 votes 5 votes Brij Mohan Gupta commented Jul 9, 2017 i edited by Brij Mohan Gupta Jul 18, 2017 reply Follow Share Please, some one explain to me why option B is undecidable because CFG is closed under emptiness? and Σ∗ is countable so simply it will be Decidable. –1 votes –1 votes iarnav commented Oct 30, 2017 reply Follow Share Third is Regularity for REC. Why is it REC and not RE asTM deals with RE and always halting TM deals with REC @Gate Keeda 0 votes 0 votes set2018 commented Nov 2, 2017 reply Follow Share Brij Mohan Gupta in second option it is universality problem ,it is undecidable for cfl but decidable for dcfl. 1 votes 1 votes set2018 commented Nov 2, 2017 reply Follow Share iarnav Regularity problem is undecidable for both REC & RE 1 votes 1 votes iarnav commented Nov 2, 2017 reply Follow Share thank you. 0 votes 0 votes Sandeep Suri commented Dec 27, 2017 reply Follow Share Can anyone explain why option 2 is undecidable and what does option 2 means? 0 votes 0 votes 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.