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
- 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
- K can be finite. I don't know how to solve this. Any Ideas?