0 votes 0 votes Consider the following language: $L$ $=$ { $<M>$ $|$ $L(M)$ has atleast $10$ strings } Which of the following is true about L? A)L is decidable B)L is Turing recognizable C)L is not recursive D)None of these Theory of Computation theory-of-computation test-series identify-class-language multiple-selects + – Pranavpurkar asked Nov 16, 2022 Pranavpurkar 438 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Chandrabhan Vishwa 1 commented Nov 16, 2022 reply Follow Share option C 0 votes 0 votes Pranavpurkar commented Nov 16, 2022 reply Follow Share Chandrabhan Vishwa 1 its msq, both b and c , reason? 0 votes 0 votes yuvrajeyes commented Nov 17, 2022 reply Follow Share @Pranavpurkar, Turing Recognizable means Recursive Enumerable Language and that language is Recursive Enumerable. If you have doubt then you can check Rice theorem for this. 0 votes 0 votes Pranavpurkar commented Nov 17, 2022 i edited by Pranavpurkar Nov 17, 2022 reply Follow Share @yuvrajeyesOkay got it! 0 votes 0 votes MANSI_SOMANI commented Nov 23, 2022 reply Follow Share Why it's not decidable? Cant we easily check whether 10 strings there or not (it's finite) ? 0 votes 0 votes Pranavpurkar commented Nov 23, 2022 i edited by Pranavpurkar Nov 23, 2022 reply Follow Share MANSI_SOMANIsee here we can have 2 languages L1 = $\phi$ in which no string is present andL2 = $\sum *$ which can generate more than 10 strings.Thus it is not always true.'moreover hereL(M) is REL , so we have some REL which can generate 10 strings and some which cannot as given in examples above ,Thus it is a non trivial property , hence undecidable. 0 votes 0 votes MANSI_SOMANI commented Nov 23, 2022 reply Follow Share @Pranavpurkar M thinking like check if u have 10 strings if it's then yes and less than 10 strings there then simply no then by rice's theorem isn't it decidable? 0 votes 0 votes Pranavpurkar commented Nov 23, 2022 reply Follow Share no it’s a non trivial property , you can refer, https://gatecse.in/rices-theorem/ 0 votes 0 votes MANSI_SOMANI commented Nov 23, 2022 reply Follow Share @Pranavpurkar Got it Thanks for sharing! We can conclude this question from the link u sended as it's undecidable but it's turing recognizable right?? 0 votes 0 votes Pranavpurkar commented Nov 23, 2022 reply Follow Share Yes . 1 votes 1 votes Please log in or register to add a comment.