1,017 views
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

2 Answers

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
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 ..

Related questions

1 votes
1 votes
2 answers
1
1 votes
1 votes
1 answer
2
learner_geek asked Aug 15, 2017
1,374 views
Is complement of language same type or not decidable by CFL and recursive language or not???Grammar is ambiguous or not?Grammar in regular/CFL/rel decidable or not?