# Is the problem of deciding whether a Context free grammar generates exactly K strings is decidable?

I am reading "Introduction to Theory of Computation" by Michael Sipser. One of the exercise problems asks to verify whether the problem of deciding whether a Context free grammar generates exactly K strings is decidable?

This problem has two parts

1. K can be infinite (I know how to solve this. If the grammar has any kind of loop then it will generate infinite number of strings
thus k=infinite.
2. K can be finite. I don't know how to solve this. Any Ideas?
• What is the language? Is the language Turing-recognizable? Is the language co-Turing-recognizable? – mikeazo Oct 31 '17 at 17:27
• @mikeazo What does a Context free grammar generates? – Kishan Kumar Oct 31 '17 at 17:29
• A CFG generates strings according to the rules in the grammar. – mikeazo Oct 31 '17 at 18:06
• But you were asking whether the language is Turing recognizable – Kishan Kumar Oct 31 '17 at 18:07
• And telling the language would not help. Since we have to consider all languages(CFL) and not a particular one. – Kishan Kumar Oct 31 '17 at 18:08

As you said, if there is a cycle of variables (non-terminals), the language generated is infinite. If you can also show the converse, that is, if the language is infinite, then there exists a cycle of variables, then you can construct a machine to do the following given a finite $K$:
1. Given a context-free grammar $G$, check if it has any cycles of non-terminals.
2. If yes, then $L(G)$ is infinite, so output no; otherwise, $L(G)$ is necessarily finite (using the converse property above, which you need to prove).
3. Since the grammar generates a finite number of strings, it is safe to try all possible paths of productions starting from the starting variable. Each such path corresponds to a string in $L(G)$. Eventually, all possible paths will be exhausted (as otherwise $L(G)$ would be infinite), at which point you will have generated $L(G)$. If $|L(G)| = K$, output yes, otherwise output no.