Determining if a langage defined by a given context-free grammar is finite using the pumping lemma Here is a question that I found into an old exam:


  Describe an algorithm that, given a context-free grammar $G$, can determine if the language $L(G)$ produced by $G$ is finite or infinite.
  Hint: use the pumping lemma.


While I found several possible solutions to the problem (mostly exploiting the presence or non-presence of cycles in the grammar or automata) none of them implies the use of the pumping lemma (that was given as hist).
For this reason I believe that none of the solutions that I found corresponds to the intended one.   

Is there any way an algorithm could exploit the pumping lemma in order to solve this problem?
Here is the corresponding result for regular languages:


  Given a DFA with $n$ states, its corresponding language is infinite iff it contains a word whose length is between $n$ and $2n-1$.


This implies an inefficient algorithm for determining whether the language is infinite.

The proof uses the pumping lemma in its following formulation:


  If a regular language $L$ is accepted by a DFA with $n$ states, then any word $w \in L$ of length at least $n$ can be decomposed as $w = xyz$, where $|xy| \leq n$ and $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$.


In one direction, if the DFA accepts some word $w$ of length at least $n$, then the pumping lemma shows that there is some decomposition $w = xyz$ with $y \neq \epsilon$ such that the infinitely many words $xy^iz$ belong to the language.

In the other direction, if the language is infinite then it contains some word whose length is at least $n$. Let $w$ such a word of minimal length. The pumping lemma show that there exists a decomposition $w = xyz$, with $0 &lt; |y| \leq n$, such that $xz$ is in the language. Since $|xz| &lt; |xyz|$, it follows that $|xz| &lt; n$, and so $|w| = |xyz| &lt; 2n$.

If you use the pumping lemma for context-free languages in a formulation in which the pumping constant is related to the size of a context-free grammar for the language, then you can use similar reasoning to come up with an algorithm that determines whether the language generated by a context-free grammar is infinite.