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

Question

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?

Answer 1

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.