3 votes 3 votes C = { <G,k> | G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be- a) decidable b) Turing unrecognizable c) Recursive enumerable d) undecidable Theory of Computation decidability context-free-language recursive-and-recursively-enumerable-languages turing-machine + – amrendra pal asked Aug 22, 2017 amrendra pal 1.0k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Manu Thakur commented Sep 9, 2017 reply Follow Share It's a decidable problem, i don't know the reason, but I noted down it from somewhere in my notebook. 0 votes 0 votes Hemant Parihar commented Sep 9, 2017 reply Follow Share We provide a grammar to a Turing machine. Then It can easily identify whether it is context free or not. Because the rule of Context free grammar is already defined. Now we need to know that how many strings present in this language. We already know that the problem whether the Context-free language is finite is decidable. If it is finite we can count and write. So I think this problem is decidable. 2 votes 2 votes Please log in or register to add a comment.
2 votes 2 votes Decidable because finiteness property for cfg is decidable but inconvenient option because if it is kind of decidabilty question then ans is decadable otherwise it REL and also REC Gatecoder answered Sep 26, 2017 Gatecoder comment Share Follow See 1 comment See all 1 1 comment reply Deependra Vivek Sing commented Oct 9, 2018 reply Follow Share if this question was for turing machine ans would be non rel right? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes It is Given that iit is a CFG and Language will be CFL and we know that for every CFL there exists a PDA which accept it. PDA is decidable . SO answer will be decidable .. Smishra95 answered Oct 9, 2018 Smishra95 comment Share Follow See all 0 reply Please log in or register to add a comment.