Return to Answer

Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in reduced form. That is,

1. every non-terminal appears in at least one derivation (starting from the initial non-terminal), and
2. every non-terminal produces at least one terminal string.

Then, $L(G)$ is infinite if and only if there is a non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$ for some $\alpha \cdot \beta \in (N \cup T)^+$.

Sketch of proof: For one direction, we have that $L(G)$ is infinite. Assume there was no such non-terminal; then there are only finitely many derivations by the pigeon-hole principle, which is a contradiction.
For the reverse, we have that there is such a non-terminal. Then, we know that $A$ can be derived to $\alpha^i A \beta^i$ for all $i \in \mathbb{N}$, and all these are distinct and derive to distinct terminal strings. Hence, $A$ alone generates an infinite set of substrings of strings in $L(G)$; therefore, $L(G)$ is infinite as well.

It's obvious that this criterion can be decided algorithmically; check for cycles of weight $> 0$ in the (multi-)graph made up of non-terminals as nodes, edges from $A$ to $B$ if $B$ appears on a right-hand-side of a rule for $A$, and weights are the number of terminals generated by these rules. Hence, the given problem is decidable.

1. We know that there is such a grammar for every context-free language; there are even effective procedures for reducing grammars and removing $\varepsilon$-rules.
2. Except maybe $S \to \varepsilon$ iff $\varepsilon \in L(G)$, and then $S$ can not appear on the right-hand side of any rule.

Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in reduced form. That is,

1. every non-terminal appears in at least one derivation (starting from the initial non-terminal), and
2. every non-terminal produces at least one terminal string.

Then, $L(G)$ is infinite if and only if there is a non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$ for some $\alpha \cdot \beta \in (N \cup T)^+$.

Sketch of proof: For one direction, we have that $L(G)$ is infinite. Assume there was no such non-terminal; then there are only finitely many derivations by the pigeon-hole principle, which is a contradiction.
For the reverse, we have that there is such a non-terminal. Then, we know that $A$ can be derived to $\alpha^i A \beta^i$ for all $i \in \mathbb{N}$, and all these are distinct and derive to distinct terminal strings. Hence, $A$ alone generates an infinite set of substrings of strings in $L(G)$; therefore, $L(G)$ is infinite as well.

It's obvious that this criterion can be decided algorithmically; check for cycles of weight³ $> 0$ in the (multi-)graph made up of non-terminals as nodes, edges from $A$ to $B$ if $B$ appears on a right-hand-side of a rule for $A$, and weights are the number of terminals generated by these rules. Hence, the given problem is decidable.

1. We know that there is such a grammar for every context-free language; there are even effective procedures for reducing grammars and removing $\varepsilon$-rules.
2. Except maybe $S \to \varepsilon$ iff $\varepsilon \in L(G)$, and then $S$ can not appear on the right-hand side of any rule.
3. If we eliminate chain rules $A \to B$ as well (a standard exercise), any cycle suffices.

Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in reduced form. That is,

1. every non-terminal appears in at least one derivation (starting from the initial non-terminal), and
2. every non-terminal produces at least one terminal string.

Then, $L(G)$ is infinite if and only if there is a non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$ for some $\alpha \cdot \beta \in (N \cup T)^+$.

Sketch of proof: For one direction, we have that $L(G)$ is infinite. Assume there was no such non-terminal; then there are only finitely many derivations by the pigeon-hole principle, which is a contradiction.
For the reverse, we have that there is such a non-terminal. Then, we know that $A$ can be derived to $\alpha^i A \beta^i$ for all $i \in \mathbb{N}$, and all these are distinct and derive to distinct terminal strings. Hence, $A$ alone generates an infinite set of substrings of strings in $L(G)$; therefore, $L(G)$ is infinite as well.

1. We know that there is such a grammar for every context-free language; there are even effective procedures for reducing grammars and removing $\varepsilon$-rules.
2. Except maybe $S \to \varepsilon$ iff $\varepsilon \in L(G)$, and then $S$ can not appear on the right-hand side of any rule.

Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in reduced form. That is,

1. every non-terminal appears in at least one derivation (starting from the initial non-terminal), and
2. every non-terminal produces at least one terminal string.

Then, $L(G)$ is infinite if and only if there is a non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$ for some $\alpha \cdot \beta \in (N \cup T)^+$.

Sketch of proof: For one direction, we have that $L(G)$ is infinite. Assume there was no such non-terminal; then there are only finitely many derivations by the pigeon-hole principle, which is a contradiction.
For the reverse, we have that there is such a non-terminal. Then, we know that $A$ can be derived to $\alpha^i A \beta^i$ for all $i \in \mathbb{N}$, and all these are distinct and derive to distinct terminal strings. Hence, $A$ alone generates an infinite set of substrings of strings in $L(G)$; therefore, $L(G)$ is infinite as well.

It's obvious that this criterion can be decided algorithmically; check for cycles of weight $> 0$ in the (multi-)graph made up of non-terminals as nodes, edges from $A$ to $B$ if $B$ appears on a right-hand-side of a rule for $A$, and weights are the number of terminals generated by these rules. Hence, the given problem is decidable.

1. We know that there is such a grammar for every context-free language; there are even effective procedures for reducing grammars and removing $\varepsilon$-rules.
2. Except maybe $S \to \varepsilon$ iff $\varepsilon \in L(G)$, and then $S$ can not appear on the right-hand side of any rule.

Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in reduced form; that is, all non-terminals can not appear in a derivation from the initial nonterminal, and from all, at least one terminal string can be derived.

Then, $L(G)$ is infinite if and only if there is a non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$ for some $\alpha \cdot \beta \in (N \cup T)^+$.

Sketch of proof: For one direction, we have that $L(G)$ is infinite. Assume there was no such non-terminal; then there are only finitely many derivations by the pigeon-hole principle, which is a contradiction.
For the reverse, we have that there is such a non-terminal. Then, we know that $A$ can be derived to $\alpha^i A \beta^i$ for all $i \in \mathbb{N}$, and all these are distinct and derive to distinct terminal strings. Hence, $A$ alone generates an infinite set of substrings of strings in $L(G)$; therefore, $L(G)$ is infinite as well.

1. We know that there is such a grammar for every context-free language; there are even effective procedures for reducing grammars and removing $\varepsilon$-rules.
2. Except maybe $S \to \varepsilon$ iff $\varepsilon \in L(G)$, and then $S$ can not appear on the right-hand side of any rule.

Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in reduced form. That is,

1. every non-terminal appears in at least one derivation (starting from the initial non-terminal), and
2. every non-terminal produces at least one terminal string.

Then, $L(G)$ is infinite if and only if there is a non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$ for some $\alpha \cdot \beta \in (N \cup T)^+$.

Sketch of proof: For one direction, we have that $L(G)$ is infinite. Assume there was no such non-terminal; then there are only finitely many derivations by the pigeon-hole principle, which is a contradiction.
For the reverse, we have that there is such a non-terminal. Then, we know that $A$ can be derived to $\alpha^i A \beta^i$ for all $i \in \mathbb{N}$, and all these are distinct and derive to distinct terminal strings. Hence, $A$ alone generates an infinite set of substrings of strings in $L(G)$; therefore, $L(G)$ is infinite as well.

1. We know that there is such a grammar for every context-free language; there are even effective procedures for reducing grammars and removing $\varepsilon$-rules.
2. Except maybe $S \to \varepsilon$ iff $\varepsilon \in L(G)$, and then $S$ can not appear on the right-hand side of any rule.