Determining if a langage defined by a given context-free grammar is finite using the pumping lemma

Question

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?

Answer 1

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 < |y| \leq n$, such that $xz$ is in the language. Since $|xz| < |xyz|$, it follows that $|xz| < n$, and so $|w| = |xyz| < 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.