Ambiguity, Equivalence, and Other Undecidable Grammar Questions

For a context-free grammar, some questions are answerable and some are not, and the boundary does not fall where intuition suggests. Membership is decidable in cubic time. Emptiness is decidable in linear time. Equivalence — do two grammars generate the same language — is undecidable. The same undecidability holds for ambiguity, for whether a grammar generates all of Σ*, and for whether two grammars are disjoint.

The decidable floor

Start with what can be computed. These problems are decidable for any context-free grammar given explicitly:

• Membership. w ∈ L(G)? CYK runs in O(n³) on a grammar in Chomsky normal form, as Chomsky Normal Form and the CYK Table shows. Earley’s algorithm matches the bound without requiring the normal form.
• Emptiness. L(G) = ∅? Compute the set of generating nonterminals — those that derive some terminal string — by iterating from the terminal rules. The language is empty exactly when S is not generating. The computation is a least fixed point over the rule set and takes time linear in the grammar size.
• Finiteness. Is L(G) finite? Restrict to generating and reachable nonterminals, then look for a cycle in the dependency graph where a nonterminal derives a sentential form containing itself. A cycle means infinitely many strings; no cycle means the language is finite, and its maximum length is computable.
• A single string’s ambiguity. Does w have two distinct parse trees? Run a modified CYK that counts derivations per cell, saturating at 2. The count is finite for a fixed w because a derivation of w has bounded length once useless and cyclic nonterminal chains are removed.

The common structure in all four: they quantify over a finite search space. CYK searches substrings of a fixed string; emptiness searches the nonterminal set; finiteness searches a graph for cycles; per-string ambiguity searches a table of size n².

Where the finite search space disappears

Equivalence asks whether L(G₁) = L(G₂) for two grammars. The natural approach is to search for a distinguishing string, and the search space is all of Σ*, which is infinite and unbounded in a way the previous problems are not. No finite table bounds it.

The reduction is from the Post Correspondence Problem. PCP asks, given a finite list of domino pairs (uᵢ, vᵢ) over some alphabet, whether there is a sequence of indices i₁…iₖ such that u_{i₁}…u_{iₖ} = v_{i₁}…v_{iₖ}. PCP is undecidable, and the standard reduction constructs, from a PCP instance, two context-free grammars whose languages are equal exactly when the instance has no solution. The grammars encode the two sides of the candidate correspondence, and the equality of the languages is equivalent to the absence of any matching sequence. Because the construction is effective and PCP is undecidable, equivalence is undecidable.

The consequence for tools is immediate: a grammar-equivalence checker cannot be total. Any program that compares two context-free grammars either answers “not equivalent” on some equivalent pair, or loops forever, or refuses some inputs. There is no fourth option, and this is a theorem rather than an engineering limitation.

Ambiguity is undecidable, and the proof is a corollary

Deciding whether a given context-free grammar is ambiguous is undecidable. The reduction goes through PCP as well, and the shape of the argument is worth understanding because it explains why per-string ambiguity is decidable while grammar ambiguity is not.

Construct a grammar G that generates all strings of the form

x # yᴿ

where x and y are sequences of domino indices and # is a fresh separator, with the additional structure that a derivation can pair the indices of x with those of y in two different orders. If the PCP instance has a solution, the grammar has two distinct parse trees for at least one string, because the same matching sequence can be read in two structural ways. If the instance has no solution, every string has a unique parse tree.

The quantification is the difference. Per-string ambiguity asks “does this w have two trees”, a finite question. Grammar ambiguity asks “does some w have two trees”, a question over an infinite set, and the existential quantifier over Σ* is what makes it undecidable.

A related and equally surprising result: it is undecidable whether a context-free grammar generates Σ*, and undecidable whether two context-free grammars generate disjoint languages. The complement of a context-free language need not be context-free, as Closure Gaps in Context-Free Languages sets out, and the missing complement is what blocks the usual reduction of universality to emptiness.

Determinism moves the boundary

Restricting to deterministic context-free languages changes the answer. Equivalence of deterministic pushdown automata is decidable — a result due to Sénizergues, with a very high complexity bound, later improved but still impractical. Equivalence of deterministic finite automata is decidable in polynomial time, by minimising both and comparing the results, or by a product construction on pairs of states. Ambiguity is vacuous for a deterministic grammar, since determinism gives every string at most one parse tree.

The pattern is general: determinism converts an unbounded search over strings into a bounded comparison of machine states, because a deterministic machine’s behaviour on a string is a single path rather than a set of paths. Where nondeterminism is essential to the formalism’s power, the decision problems become undecidable; where it can be removed without losing the language, they often become decidable again.

The practical form of this is that parser generators do not check equivalence of arbitrary grammars. They check for conflicts in a deterministic parsing table, which is a decidable, local property of the grammar and its lookahead sets. A grammar with no conflicts is LR(1); a grammar with conflicts may still be unambiguous, but the tool cannot tell, and it reports the conflict rather than an ambiguity verdict.

Living with the boundary

The undecidability results do not make grammar tools useless. They constrain what such a tool can promise, and the standard responses are:

Sound but incomplete checks. A tool can report “these two grammars are equivalent” only when it finds a proof — a bisimulation, a common normal form, a syntactic identity after transformation. It never claims the negative for an arbitrary pair. The answer set is a subset of the true equivalences, which is exactly what a semi-decision procedure provides.

Restriction to a decidable subclass. Equivalence is decidable for regular grammars, for deterministic context-free grammars, and for various bounded and visibly-pushdown subclasses. A tool that accepts only these is total on its input domain and rejects the rest at parse time.

Bounded search. Ambiguity can be tested for all strings up to a length bound, and the test is complete for that bound. A grammar that is unambiguous up to length k may still be ambiguous at length k+1, so the result is a heuristic, but a useful one: many naturally occurring ambiguities have short witnesses.

from itertools import product

# Bounded ambiguity test: is there a string of length <= max_len with two parses?
# Complete for the bound, silent about longer strings.
def count_parses(grammar, start, word, cap=2):
    """Parse trees for `word`, saturated at `cap`. Grammar in Chomsky normal
    form: {A: {(sym,), (B, C), ...}}."""
    n = len(word)
    if n == 0:
        return 1 if () in grammar.get(start, ()) else 0
    t = [[{} for _ in range(n)] for _ in range(n)]
    for i, ch in enumerate(word):
        for lhs, rules in grammar.items():
            if (ch,) in rules:
                t[i][i][lhs] = min(cap, t[i][i].get(lhs, 0) + 1)
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                for lhs, rules in grammar.items():
                    for r in rules:
                        if len(r) == 2:
                            a = t[i][k].get(r[0], 0)
                            b = t[k + 1][j].get(r[1], 0)
                            if a and b:
                                t[i][j][lhs] = min(cap, t[i][j].get(lhs, 0) + a * b)
    return t[0][n - 1].get(start, 0)

def ambiguous_within(grammar, start, max_len):
    alphabet = sorted({s for rules in grammar.values() for r in rules
                       for s in r if s not in grammar})
    for length in range(max_len + 1):
        for tup in product(alphabet, repeat=length):
            w = ''.join(tup)
            if count_parses(grammar, start, w) >= 2:
                return w
    return None

The saturation at cap is the essential detail: without it the count overflows any fixed-width integer for modest lengths, because the number of trees grows as fast as the Catalan numbers for a grammar like S → SS | a.

Reframing the question. Instead of asking whether a grammar is ambiguous, ask whether the parser accepts the intended language on the inputs that matter. That is a testing question, decidable by construction, and it is the one that a grammar author actually needs answered.

Why these particular questions are the undecidable ones

There is a pattern in which problems survive. Membership and emptiness are decidable because they are existential questions with finite witnesses: a derivation of w has bounded length, and a generating nonterminal has a finite derivation. Equivalence and ambiguity are undecidable because they are questions about all strings, and a universal quantifier over an infinite set cannot be discharged by a finite search unless the structure of the language collapses the set to finitely many cases.

Regular languages collapse that set: Myhill–Nerode gives finitely many equivalence classes, so “for all w” becomes “for all classes”. Context-free languages do not, and no analogous finite index exists. The undecidability of equivalence and ambiguity is the price of that missing collapse, and it is the same price that type 1 and type 0 grammars pay more heavily, as The Chomsky Hierarchy as a Ladder of Memory sets out.