3 votes 3 votes a) L is decidable b) L is undecidable c) L is regular d) None of these Theory of Computation decidability context-free-language turing-machine reduction + – Nymeria asked Jan 10, 2018 Nymeria 940 views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Ashwin Kulkarni commented Jan 10, 2018 reply Follow Share L is decidable. 0 votes 0 votes Nymeria commented Jan 10, 2018 reply Follow Share but the answer given is l is undecidable. So can i safely assume given answer is incorrect? 0 votes 0 votes Ashwin Kulkarni commented Jan 10, 2018 reply Follow Share see this Question : https://gateoverflow.in/15024/s1-l-≤-m-0n1n-n-≥-0-then-l-is-decidable 0 votes 0 votes Sandeep Suri commented Jan 10, 2018 reply Follow Share L is decidable maybe answer is incorrect can you share what explanation they have given to show it as undecidable 0 votes 0 votes Anu007 commented Jan 10, 2018 i edited by Anu007 Jan 10, 2018 reply Follow Share L is undecidable! 0 votes 0 votes Sandeep Suri commented Jan 10, 2018 reply Follow Share How? 0 votes 0 votes Anu007 commented Jan 10, 2018 reply Follow Share I am giving CFL to computer and ask it will accept it or not, it is same as halting problem. 1 votes 1 votes Ashwin Kulkarni commented Jan 10, 2018 reply Follow Share @Anu sir, it is decidable L(m) is reduced to decidable language hence L(m) is also decidable. Please visit that link which i have shared above. 0 votes 0 votes Anu007 commented Jan 10, 2018 reply Follow Share problem in link is decidable but here probelem related to TM , it is undecidable. you know given regular language to TM , TM accept it or not is undecidable i.e. regularity problem. 2 votes 2 votes Nymeria commented Jan 11, 2018 reply Follow Share @sandeep suri i don't have the explanation. just the answer. 0 votes 0 votes Nymeria commented Jan 11, 2018 reply Follow Share @anu007 got it sir. thank you so much :) 1 votes 1 votes Soumya29 commented Jan 12, 2018 reply Follow Share @Anu007 Can we apply Rice theorem here? If yes. Then can we take it as L(Tyes)= 1(0^p)1(1^2p) (any CFL reducable to 0^p1^2p) and L(Tno)= sigma* ? 0 votes 0 votes reboot commented Jul 18, 2020 reply Follow Share Duplicate question: https://gateoverflow.in/76610/decidability 0 votes 0 votes Please log in or register to add a comment.