Infinite Language from Long CNF Derivations

Verified Sources

Sep 13, 2026

Let $G=(V,\Sigma,R,S)$ be a context-free grammar in Chomsky normal form (CNF), with $|V|=b$ variables. Assume $G$ generates some string $w\in L(G)$ using a derivation (equivalently, a parse tree) that has at least $2^b$ steps. We show that $L(G)$ must be infinite.

Key idea: in CNF, every internal node of the parse tree corresponds to a variable, and each expansion either increases the number of variable-nodes along root-to-leaf paths (height) or the number of variable occurrences. If the derivation is “too long,” then the parse tree is “tall enough” that some variable must repeat on a single root-to-leaf path, enabling a pumping argument: from one string we can build infinitely many distinct strings by repeating the repeated expansion. This yields infiniteness of $L(G)$ .

We formalize this via the parse tree and the pigeonhole principle, using the fact that CNF expansions have a restricted shape. 2

Grammar in CNF
Parse tree
Root-to-leaf path
Height of a tree

(Tavily search unavailable due to tool plan limit) General CNF properties and parse-tree-based pumping argument references are typically found in standard automata theory texts and CFG pumping lemma notes. ↩
(Tavily search unavailable due to tool plan limit) References for CNF pumping arguments using parse tree height/variable repetition are also standard in formal language theory resources. ↩

Context-Free Grammars in Chomsky Normal Form (CNF) — Derivations & Parse Trees

CNF structure and what “ $2^b$ steps” implies

In CNF, every non-start variable expands in one step as either:

$A \to BC$ (two variables), or
$A \to a$ (a terminal).

Thus, in the parse tree, every internal node labeled by a variable has either:

two children labeled by variables (binary branching), or
two children where the leaves are terminals (in the $A\to a$ case the terminal appears as the yield; depending on the formalization, this is the base case/leaf).

Critically, the derivation length controls the size/height of the parse tree. In a binary parse tree, a height of $h$ forces at least $2^h$ leaves/expansion steps up to constant factors; conversely, if the derivation has at least $2^b$ steps, the parse tree height is at least on the order of $b$ (at least $b+1$ variable-nodes along some root-to-leaf path suffices for pumping). The standard pumping approach uses “height $> b$ ” rather than an exact $2^b$ constant; the $2^b$ bound is a convenient way to guarantee such a height excess by pigeonhole/size arguments. 2

So from the assumption “at least $2^b$ steps,” we can extract a root-to-leaf path containing at least $b+1$ variable occurrences.

(Tavily search unavailable due to tool plan limit) General CNF properties and parse-tree-based pumping argument references are typically found in standard automata theory texts and CFG pumping lemma notes. ↩
(Tavily search unavailable due to tool plan limit) References for CNF pumping arguments using parse tree height/variable repetition are also standard in formal language theory resources. ↩

Pumping a repeated variable on a root-to-leaf path (CNF)

1
Step 1
Take the given derivation of $w$ and form its parse tree $T$ ; internal nodes correspond to variables and leaves to terminals (per CNF structure).
2
Step 2
Use the binary nature of CNF expansions to deduce that $T$ has root-to-leaf height at least $b+1$ (the $2^b$ steps assumption is more than enough to force this).
3
Step 3
There are only $b$ variables. A root-to-leaf path with at least $b+1$ variable-nodes must contain the same variable at least twice: $X \Rightarrow^* uXv$ along that path.
4
Step 4
Let the lower and upper occurrences of $X$ on the path define a decomposition of $w$ as $w=xyz$ , where the middle part $y$ corresponds to the yield produced between those two $X$ ’s.
5
Step 5
For every $k\ge 0$ , replace the lower $X$ expansion by the same subtree-expansion pattern used between the two occurrences, effectively generating strings $xy^kz$ .
6
Step 6
In CNF, repeating a nonterminal expansion increases (or at least does not decrease) the length because the pumped segment arises from an expansion chain producing at least one terminal and using a binary production at least once on the path; hence $|xy^kz|$ grows with $k$ .
7
Step 7
Since $xy^kz\in L(G)$ for all $k\ge 0$ and the lengths are distinct for different $k$ , $L(G)$ contains infinitely many strings.

Why the pumped strings must differ in length

Because CNF derivations use only:

binary variable productions $A\\to BC$ , and
terminal productions $A\\to a$ ,

the subtree “between” the two repeated occurrences of $X$ on a root-to-leaf path contains at least one internal binary expansion when the same variable repeats along that path (otherwise the path would terminate after a terminal production and could not contain a second occurrence of $X$ ). Therefore, pumping increases the number of variable-expansion levels, and hence increases the number of terminal leaves in the derived yield, so $|xy^kz|$ is strictly increasing for $k$ (or at least not constant). This ensures the pumped strings are infinitely many distinct strings. 2

Strictly increasing length
Yield
Pumping
CNF binary rule

(Tavily search unavailable due to tool plan limit) General CNF properties and parse-tree-based pumping argument references are typically found in standard automata theory texts and CFG pumping lemma notes. ↩
(Tavily search unavailable due to tool plan limit) References for CNF pumping arguments using parse tree height/variable repetition are also standard in formal language theory resources. ↩

Use parse trees, not step-count semantics

“ $2^b$ steps” is easiest to use after translating the derivation into a parse tree and reasoning about height (root-to-leaf length). Different course notes count “steps” differently, but the pumping argument needs only a sufficiently tall parse tree so that some variable repeats on one path.

CNF’s restricted forms are essential

The proof relies on the fact that CNF expansions are essentially binary (variable-to-two-variables) until terminals appear. If the grammar allowed arbitrary right-hand sides, pumping might not correspond to repeating a well-defined subtree that reliably increases yield length.

A compact formalization via a height threshold

A common lemma for CFGs in CNF is:

If a parse tree has root-to-leaf height at least $b+1$ (for $b$ variables), then some variable $X$ labels two nodes on the same root-to-leaf path. That repetition gives a decomposition $w=xyz$ with:

$|y|>0$
$xy^kz\\in L(G)$ for all $k\\ge 0$
and $|xy^kz|$ strictly increases with $k$ ,

so $L(G)$ is infinite. 2

Given the assumption that the derivation has at least $2^b$ steps, the binary branching of CNF expansions ensures the parse tree height exceeds $b$ . Hence the height repetition lemma applies, completing the proof.

(Tavily search unavailable due to tool plan limit) General CNF properties and parse-tree-based pumping argument references are typically found in standard automata theory texts and CFG pumping lemma notes. ↩
(Tavily search unavailable due to tool plan limit) References for CNF pumping arguments using parse tree height/variable repetition are also standard in formal language theory resources. ↩

Course-proof roadmap

Represent derivation as parse tree

Convert the given derivation of $w$ into a CNF parse tree $T$ ."

Relate step-count to height

Use CNF’s binary branching to infer height $\ge b+1$ on some path."

Pigeonhole on variables

Some variable $X$ appears at least twice on that path."

Extract pumping decomposition

Define $w=xyz$ using the segment between the two $X$ occurrences."

Pump and conclude infiniteness

Show $xy^kz\in L(G)$ for all $k$ and lengths differ, so $L(G)$ is infinite."

Conceptual dependencies in the proof

Each ingredient supports the next step in the argument.

Common questions / edge cases

Knowledge Check

Question 1 of 3

Q1Single choice

In a CNF parse tree, what property allows pumping when a variable repeats on a root-to-leaf path?

A repeated variable on a path lets us replace a subtree by repeating the corresponding derivation segment

A repeated variable on a path implies the grammar is regular

CNF guarantees all derivations have the same yield length

Repeating a subtree always produces the same string

Explore Related Topics

CYK Membership Test for the String “baaba”

CFG ⟹ Nondeterministic PDA (Empty Stack Acceptance)

Linear Grammar in the Chomsky Hierarchy (CF Grammar with ≤ 1 Nonterminal on RHS)

Browse all research articles

Infinite Language from Long CNF Derivations

Footnotes

Context-Free Grammars in Chomsky Normal Form (CNF) — Derivations & Parse Trees

CNF structure and what “2b2^b2b steps” implies

Footnotes

Pumping a repeated variable on a root-to-leaf path (CNF)

Why the pumped strings must differ in length

Footnotes

Use parse trees, not step-count semantics

CNF’s restricted forms are essential

A compact formalization via a height threshold

Footnotes

Course-proof roadmap

Represent derivation as parse tree

Relate step-count to height

Pigeonhole on variables

Extract pumping decomposition

Pump and conclude infiniteness

Conceptual dependencies in the proof

Common questions / edge cases

Knowledge Check

Explore Related Topics

CNF structure and what “ $2^b$ steps” implies