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?
  • $\begingroup$ What is the language? Is the language Turing-recognizable? Is the language co-Turing-recognizable? $\endgroup$ – mikeazo Oct 31 '17 at 17:27
  • $\begingroup$ @mikeazo What does a Context free grammar generates? $\endgroup$ – Kishan Kumar Oct 31 '17 at 17:29
  • $\begingroup$ A CFG generates strings according to the rules in the grammar. $\endgroup$ – mikeazo Oct 31 '17 at 18:06
  • $\begingroup$ But you were asking whether the language is Turing recognizable $\endgroup$ – Kishan Kumar Oct 31 '17 at 18:07
  • $\begingroup$ And telling the language would not help. Since we have to consider all languages(CFL) and not a particular one. $\endgroup$ – 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.