JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Undecidable Already: Ambiguity and Equivalence

You can always decide whether a grammar generates a given string, and whether it generates anything at all — but you can never, by any algorithm, decide whether two grammars describe the same language, or whether a grammar is ambiguous. Undecidability does not wait for Turing machines; it is already lurking inside the humble context-free grammar.

A line drawn through the grammar questions

The previous guide left you on solid ground: given a context-free grammar, you can always answer two questions by algorithm. Does it generate this particular string? The CYK algorithm says yes or no in O(n^3) time once the grammar is in Chomsky normal form — that is membership decidability. Does it generate anything at all? Mark which variables can reach a terminal string, propagate upward, and check the start symbol — that is emptiness decidability. Both are not merely 'solvable in principle'; they have real, terminating procedures you could code this afternoon.

Now comes the jolt. Two of the most natural questions you could possibly ask about grammars have NO algorithm at all — not a slow one, not a clever one, none, ever. Given two context-free grammars, do they generate exactly the same language? That is equivalence, and it is undecidable. Given one grammar, is it ambiguous — does some string have two different parse trees? That is ambiguity, also undecidable. The boundary between what you can decide and what you cannot runs straight through the middle of context-free grammar theory.

The seed of trouble: the Post Correspondence Problem

Where does grammar undecidability come from? It is imported, by a translation, from one undecidable problem that is tailor-made for strings: the Post Correspondence Problem, or PCP. Picture a finite set of dominoes, each printed with a top string and a bottom string, for example [a / ab], [b / a], [aba / b]. You may use each domino as many times as you like, in any order. The puzzle: can you line up a non-empty sequence of them so that reading all the tops, concatenated, gives the exact same string as reading all the bottoms?

Dominoes:   1:[ a / ab ]   2:[ b / a ]   3:[ aba / b ]

Try sequence  3 , 2 , 3 , 1 :
  tops    :  aba   b    aba   a    =  abababa
  bottoms :  b     a    b     ab   =  babbab ...   (mismatch)

Finding ANY matching sequence is the puzzle.
PCP asks: does a match exist for THIS set of dominoes?
That yes/no question has NO general algorithm.
The Post Correspondence Problem: can some non-empty domino sequence make the concatenated tops equal the concatenated bottoms? Deciding this for an arbitrary domino set is undecidable.

PCP looks like an innocent word game, yet deciding whether a given domino set has any match is undecidable — proved by reducing the halting problem to it, so that a hypothetical PCP-solver would secretly solve halting. This is the same machinery you met before: a reduction is a translator that turns one problem into another, and if the source problem has no algorithm, neither can the target. PCP is the bridge from raw Turing-machine undecidability into the world of strings and concatenation — and grammars live in exactly that world.

From dominoes to grammars: building two languages of 'matches'

Here is the elegant trick that smuggles PCP into grammar theory. Given any domino set, you can mechanically write down two context-free grammars. One grammar, call it G-top, generates all strings of the form (a sequence of domino indices) followed by (the concatenation of the corresponding TOP strings, reversed and tagged). The other, G-bottom, does the same using the BOTTOM strings. The construction is rote — each domino becomes a few production rules — and crucially, each side really is context-free, because matching a sequence against its own reversal is just the palindrome-style stacking a single stack handles.

Now watch the two languages collide. A string can be generated by BOTH grammars — it lies in their intersection — exactly when its index sequence makes the tops concatenation equal the bottoms concatenation. In other words, the languages L(G-top) and L(G-bottom) share a common string if and only if the domino set has a PCP match. The whole undecidability of PCP has been re-expressed purely in terms of two context-free grammars and whether their languages overlap.

This is the payoff of the closure lesson from earlier in this rung: the context-free languages are NOT closed under intersection, and here is that very gap weaponised. If you HAD an algorithm to test whether two CFGs share a string, you could run it on G-top and G-bottom and thereby decide PCP — which is impossible. So no such algorithm exists. From this single seed, the undecidability of equivalence, ambiguity, and several cousin problems all sprout, by short further reductions.

Why equivalence and universality fall

The reduction direction matters, so trace it carefully. A reduction proves a target problem is hard only when it runs FROM a known-hard problem TO the target. We have a known-hard string question (do two CFGs share a string?), and we want to convict equivalence. Equivalence asks: is L(G1) = L(G2)? It turns out the closely related universality problem — does a grammar generate ALL strings over its alphabet, i.e. L(G) = Sigma* (the set of every possible string) — is itself undecidable, and equivalence inherits the verdict because asking 'is L(G) everything?' is just asking 'is L(G) equivalent to a grammar for Sigma*?'.

The deep reason universality (and hence equivalence) is hopeless ties back to complement. Recognising that a grammar generates everything is, in effect, recognising that the COMPLEMENT of its language is empty. But CFLs are not closed under complement, so the complement of a CFL need not be context-free — and you cannot just run the decidable emptiness test on it, because there may be no grammar to run it on. The very tool that rescued membership and emptiness (turn it into a grammar, then mark reachable symbols) is unavailable here, and no substitute exists.

Why ambiguity is undecidable too

Ambiguity gets convicted by the same PCP seed, with a clever twist. Recall that a grammar is ambiguous if some single string has two distinct parse trees (two structurally different ways to derive it). Take the PCP construction again: combine G-top and G-bottom into ONE grammar with a new start rule S → S-top | S-bottom. A string that is in both languages — that is, a PCP match — can now be derived two ways: once through the S-top branch and once through the S-bottom branch. Those are two different parse trees for one string. So the combined grammar is ambiguous if and only if a PCP match exists.

  1. Start from an arbitrary domino set — an instance of the undecidable Post Correspondence Problem.
  2. Mechanically build G-top and G-bottom, the two context-free grammars whose shared strings are exactly the PCP matches.
  3. Glue them under one start symbol: S → S-top | S-bottom. This single grammar is fully built by a finite, rote procedure.
  4. Observe: the grammar is ambiguous exactly when some string is generated both ways — i.e. exactly when the domino set has a PCP match.
  5. Conclude: an ambiguity-tester would decide PCP, which is impossible. Therefore testing ambiguity is undecidable.

Be careful about what this does and does not claim. It does NOT say every grammar is hard to inspect — for any particular grammar you may well spot an ambiguous string by hand, or prove it unambiguous by argument. Undecidability is about the absence of a SINGLE algorithm that works for ALL grammars. And it does NOT say ambiguity itself is meaningless: a related notion, an inherently ambiguous language, is one for which EVERY grammar is ambiguous — that is a property of the language, not of one grammar, and it is a separate, also-subtle fact that such languages exist.

The map at the close of the rung

Step back and survey the full landscape this rung has charted. Closure drew the map of the class; the pumping lemma proved which languages sit outside it; CYK and the emptiness test showed which questions you can answer; and now you see precisely which questions you cannot. The list of undecidable grammar problems is longer than just equivalence, ambiguity, and universality — it also includes whether a CFL is regular, whether the intersection of two CFLs is empty, and whether one CFL contains another. The PCP seed and a handful of reductions account for nearly all of them.

It is worth contrasting against the regular world one last time, because the contrast is the whole story. For finite automata, equivalence IS decidable: minimise both DFAs and compare, or test whether their symmetric difference is empty — that is the decidable equivalence problem for DFAs. The leap from finite memory to one unbounded stack is exactly the leap that turns equivalence from decidable to undecidable. The closure failure under intersection and complement was not a curiosity after all; it was the early warning that decision power would crack here too.

Where this leaves you: with a genuinely complete picture of the context-free tier. You know its grammars and its pushdown machines, the boundary of what it can express, and now the sharp edge of what it lets you compute about itself. Carry one big idea onward — undecidability is not a faraway monster requiring the full power of a Turing machine to summon; it is already sitting inside a finite list of grammar rules. When you climb into the decidability and complexity rungs above, you will meet the halting problem and the reductions that drive these proofs in their native habitat, and recognise old friends.