Counting Derivations: Algebraic Generating Functions and the Growth of Parse Trees

Membership asks whether a string is in the language. A different question asks how many ways a string is in the language, and that question turns a grammar into a system of polynomial equations. The solutions are algebraic power series, their coefficients count parse trees, and their growth rates explain why an ambiguous grammar is not merely inelegant but unusable.

Two counts that are easy to confuse

Fix a grammar G and a string w. There are three different quantities one can count:

1. The number of leftmost derivations of w, which equals the number of parse trees by the bijection in Derivations, Sentential Forms, and What a Parse Tree Actually Records.
2. The number of distinct strings of length n in L(G), which is at most |Σ|ⁿ.
3. The number of derivations of length exactly k, which counts derivations that may derive strings of different lengths.

The first and third are the ones that yield clean generating functions, and they are different series. The second is the harder object: it is not read off from the parse-tree counts, because different derivations can produce the same string.

The series used here marks terminal symbols. For a nonterminal A, let aₙ be the number of parse trees with root A whose yield has exactly n terminal symbols. Then

F_A(z) = Σ_{n≥0} aₙ zⁿ

and the grammar’s rules translate into equations relating the F_A. A rule A → X₁X₂…Xₖ becomes a product: a terminal contributes a factor z, and a nonterminal B contributes F_B. A rule A → α | β becomes a sum. The whole grammar becomes a finite polynomial system

F_A = P_A(z, F_{B₁}, …, F_{Bₘ})

and the quantity of interest is the coefficient [zⁿ] F_S.

The translation, checked on a small grammar

Take S → SS | a. The rule set gives one equation:

F = F² + z

The solution that starts at 0, which is the one with non-negative integer coefficients, is

F(z) = (1 − √(1 − 4z)) / 2 = z + z² + 2z³ + 5z⁴ + 14z⁵ + …

The coefficients are the Catalan numbers C_{n−1}: the number of full binary trees with n leaves. That matches the direct count, since a parse tree for this grammar is exactly a full binary tree with a leaves at the bottom. The closed form is available because the equation is quadratic; for a general grammar it is not, but the coefficients are always computable by iterating the system.

The iteration is a fixed-point computation on truncated series. Start with every F_A = 0, substitute into the right-hand sides, and repeat. Each round adds at least one term to each series, because every derivation has finite depth, so after n rounds the coefficients up to zⁿ are correct. The cost is O(n) rounds times the cost of one substitution over n coefficients, which is O(n²) per equation for a binary rule, so the total is O(n³) per nonterminal in the naive implementation and O(n²) with convolution.

def series_from_grammar(grammar, start, n):
    """grammar: dict A -> list of right sides; terminals are strings not in grammar.
    Returns coefficients [z^0..z^n] of the parse-tree generating function for start."""
    NT = list(grammar)
    F = {A: [0] * (n + 1) for A in NT}

    def mul(p, q):
        out = [0] * (n + 1)
        for i, pi in enumerate(p):
            if pi == 0:
                continue
            for j, qj in enumerate(q[:n + 1 - i]):
                if qj:
                    out[i + j] += pi * qj
        return out

    def rhs(A):
        total = [0] * (n + 1)
        for rule in grammar[A]:
            term = [1] + [0] * n           # multiplicative identity
            for sym in rule:
                if sym in grammar:
                    term = mul(term, F[sym])
                else:
                    term = mul(term, [0, 1] + [0] * (n - 1))   # factor z
            total = [t + s for t, s in zip(total, term)]
        return total

    for _ in range(n + 1):                 # one round per coefficient needed
        F = {A: rhs(A) for A in NT}
    return F[start]

The fixed point is reached after n + 1 rounds rather than converging numerically: the iteration is exact on truncated series, and each round is guaranteed to extend correctness by one coefficient. The if pi == 0: continue guard is a correctness-preserving shortcut that also keeps the inner loop short on the sparse series that grammars usually produce.

For S → SS | a with n = 6, the returned coefficients are 0, 1, 1, 2, 5, 14, 42 — the Catalan numbers, confirming the closed form.

Growth rate and the dominant singularity

The coefficients of an algebraic series grow exponentially with a polynomial correction. If F is algebraic and its dominant singularity is at radius ρ with local behaviour (1 − z/ρ)^α, then

[zⁿ] F ~ c · ρ^{−n} · n^{−α−1}

by the standard transfer result in singularity analysis. For the Catalan series, ρ = 1/4 and α = 1/2, so the coefficients grow as 4ⁿ · n^{−3/2}, which matches C_{n−1} ~ 4^{n−1}/(n^{3/2}√π). The exponential base 4 is the inverse of the singularity radius, and the exponent −3/2 is a signature of the square-root singularity that a quadratic equation produces.

Two facts follow that matter for parsers:

• The exponential rate is a property of the grammar’s shape, not of the language. For S → SS | a, the rate is 4 per terminal. A grammar with more binary rules or more alternatives gets a larger rate. A grammar that derives long strings through long right sides rather than binary branching gets a different rate, because each rule application contributes a different number of terminals.
• The polynomial correction does not rescue anything. The factor n^{−3/2} decays slowly, so for the lengths at which a parser is asked to work, the exponential term dominates completely. A general parser that enumerates parse trees cannot finish on inputs of moderate length, no matter how favourable the exponent. CYK avoids the enumeration by storing sets rather than trees, which is why its cubic bound is independent of the parse count.

An unambiguous grammar has a much simpler series: F_S(z) = Σ_{w ∈ L} z^{|w|}, with coefficient at zⁿ equal to the number of strings of length n, because each string has exactly one tree. Those coefficients are 0 or 1, and they are 1 at every length that the language occupies. For {aⁿbⁿ} the series is z² + z⁴ + z⁶ + …, which sums to z²/(1 − z²) — a rational function with a pole at z = 1. This is a strong constraint: the word-count series of an unambiguous context-free language is algebraic. Chomsky and Schützenberger proved the converse direction as well, in the form that a language is context-free exactly when its characteristic series is algebraic in the appropriate sense. The algebraic criterion is therefore a characterisation of the class, not merely a tool.

Chomsky–Schützenberger and the Dyck language

The structure theorem states that a language is context-free if and only if it is the homomorphic image of the intersection of a Dyck language with a regular language. The Dyck language D_m over m pairs of brackets consists of all balanced bracket sequences, generated by

S → SS | aSb | ε

for one pair, with the general m-pair version using m distinct bracket types. The theorem says every context-free language is obtained by taking a balanced-bracket language, filtering it with a finite automaton, and relabelling the symbols.

The mechanism is a bracket encoding of derivations. A derivation of a context-free grammar can be written as a sequence of events: entering a rule, processing each child in turn, and leaving the rule. That sequence is balanced, because every entry has a matching exit, and the depth of nesting is the depth of the parse tree. Different bracket types encode which rule was entered. The regular language then enforces that the sequence of rule entries is consistent with the grammar’s productions, and the homomorphism erases the brackets and keeps the terminals.

The theorem is the cleanest statement of what a stack can do. A pushdown automaton recognises exactly the balanced sequences over some bracket alphabet, filtered by finite-state control, and everything else is a relabelling. It also explains why the Dyck language is the canonical context-free language and why every context-free language reduces to it: the nesting structure is the only thing a stack can record, and the theorem says that is enough.

A consequence for the counting question: the Dyck language with one bracket pair has the Catalan generating function above, so its parse count is exactly the Catalan numbers. Any grammar whose derivations embed a Dyck structure inherits that exponential growth, which is a way to see at a glance that a grammar is heavily ambiguous.

What the growth rate diagnoses

The generating function turns a qualitative question into a quantitative one. Three diagnoses follow from the coefficients:

Bounded ambiguity. If the coefficients of F_S are bounded by a constant C, then the language has at most C strings at each length, and each such string has at most C parse trees. Both consequences follow directly: every string contributes at least one parse tree, and the coefficient is the sum of the per-string counts. The language can still be infinite, since the bound applies per length and not across lengths; the series for {aⁿbⁿ} has coefficients 0 and 1, and the language is infinite. Bounded coefficients therefore say nothing about whether the language is finite, only that the parse count does not grow with length.

Polynomial ambiguity. Some grammars have a parse count that grows polynomially in the string length for a particular string, such as n or n². The ambiguity degree of such a grammar is polynomial, and a general parser pays only a polynomial-factor penalty rather than an exponential one.

Exponential ambiguity. A grammar with a self-embedding rule that duplicates a nonterminal, such as A → AA, produces parse forests whose size grows with the exponential base determined by that rule. S → SS | a has base 4, and any grammar containing it as a reachable component inherits a factor of that growth.

The third case is the one that matters for tooling. A grammar with exponentially many parses cannot be handled by a parser that returns all of them, and the usual response is to return one parse by fixing a conflict resolution order. That selects one tree among many for the same strings and leaves the set of accepted strings unchanged; it does not remove the ambiguity from the language, which matters when the ambiguity is inherent — when every grammar for the language is ambiguous, as is the case for {aⁱbʲcᵏ : i = j or j = k} and its relatives, as Ambiguity, Equivalence, and Other Undecidable Grammar Questions discusses.

Why this is analysis and not an algorithm

The generating-function view does not decide ambiguity. A coefficient of 1 says the total number of parse trees over all strings of that length is 1, which is a statement about a sum, not about any particular string. It happens to be sufficient in one useful special case and useless in general, so the series is a diagnostic rather than a decision procedure.

What the view does provide is a fast test for one common situation. If a length-n coefficient exceeds the number of distinct strings of length n, two parse trees of that length must share a string, and the grammar is ambiguous. For a binary alphabet the number of strings of length n is 2ⁿ, so a coefficient above 2ⁿ settles the question at that length. For the grammar S → SS | a over the one-symbol alphabet {a}, there is exactly one string of each length, so any coefficient above 1 proves ambiguity immediately, and the coefficient at n = 4 is 5.

The deeper reason the analytic view cannot replace the decision procedure is the same reason grammar equivalence is undecidable: checking a property of all strings requires either a decision procedure or an unbounded search, and no finite prefix of a coefficient sequence settles such a property on its own. The algebraic structure constrains the sequence heavily — it must satisfy a polynomial equation, so a finite prefix plus the equation determines the rest — but that constraint is in the wrong direction for decision purposes: the equation fixes how many parse trees exist at each length, not how those trees distribute across strings.

The productive use of the theory is in grammar design. A grammar whose generating function has a large exponential rate is one whose parse forests are enormous, and the cost of any algorithm that touches every tree is correspondingly enormous. Choosing rules that keep the rate small, and preferring constructions that produce a single tree per string, is a design discipline that the coefficients make measurable rather than merely aesthetic.