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

Undecidable Grammar Problems

The Post correspondence problem looked like a harmless tiling puzzle. Now we cash it in: by reducing PCP TO questions about context-free grammars, we discover that asking whether a grammar is ambiguous, whether two grammars generate the same language, or whether one generates every string is undecidable. We also meet the line — some grammar questions stay perfectly decidable — and how the same reductions hit Turing-machine emptiness and equivalence.

Cashing in the Post correspondence problem

Guide 3 of this rung handed you a strange little prize: the Post correspondence problem (PCP) — given a box of domino-like tiles, each with a top string and a bottom string, can you line up some tiles (repeats allowed) so the concatenation along the top exactly equals the concatenation along the bottom? — is undecidable. That felt like a curiosity. This guide is where it pays off. PCP is the perfect crowbar: it is purely about STRINGS lining up, which is exactly what a context-free grammar is good at producing. So we will take PCP, the known-undecidable problem, and reduce it TO a string of innocent-looking questions about grammars — and watch each of those questions inherit PCP's undecidability.

Keep the direction firmly in mind, because it is the single thing beginners flip and the only thing that makes the argument valid. We are NOT trying to solve PCP. We are proving a grammar question is hard, so we reduce FROM the known-hard problem (PCP) TO the grammar question. The shape is always: 'if I had a magic box that decided this grammar question, I could feed it cleverly-built grammars and read off the answer to PCP.' Since PCP has no decider, the magic box cannot exist, so the grammar question has no decider either. Reduce the wrong way — building PCP instances to answer the grammar question — and you would prove nothing, the way a hard exam being reducible to an easy one tells you nothing about the hard one.

The bridge: turning a tile box into two grammars

Here is the one clever construction that powers almost everything below. Take any PCP instance: tiles where tile i has top string t_i and bottom string b_i, over some alphabet. We build TWO grammars from it. The 'top' grammar T_top generates exactly the strings you can read off the TOP of any valid sequence of tiles, with the sequence of tile-indices recorded at the end as a tag; the 'bottom' grammar T_bot does the same for the BOTTOM strings, with the SAME index tag. The trick is the index tag — written in reverse — so that a string the two grammars share would have to use the very same tile order on top and on bottom. Both grammars are genuinely context-free: each is just 'pick a tile, emit its string, recurse, then emit the index.'

PCP instance:  tile 1 = (top "a", bot "ab"),  tile 2 = (top "b", bot "")

T_top:  S -> a S 1 | b S 2 | a 1 | b 2        (emit a top string, tag index)
T_bot:  S -> ab S 1 |  S 2 | ab 1 | 2         (emit the bottom string, same tag)

A string in BOTH languages, e.g.  "ab" + reversed-index "21":
   top reading  a , b   uses tiles 1,2 -> tops "a"+"b" = "ab"   tag 2 1
   bot reading ab , (eps) uses tiles 1,2 -> bots "ab"+"" = "ab"  tag 2 1
=> a shared string EXISTS  <=>  the PCP match (tiles 1,2) EXISTS
A tiny PCP box becomes two context-free grammars. A string they share encodes a PCP solution: the index tag forces top and bottom to use the same tile order.

Stare at the punchline of that diagram: the two languages share a string IF AND ONLY IF the PCP instance has a match. So a magic box that could answer 'do these two context-free grammars generate any common string?' — that is, 'is the INTERSECTION of two context-free languages non-empty?' — would let us decide PCP. It does not exist, so we have just proved: testing whether two CFGs share a string is undecidable. (Note the texture: individual CFLs are well-behaved, but context-free languages are NOT closed under intersection, and this construction lives exactly in that crack. This is the reduction we now reuse, with twists, for ambiguity, universality, and equivalence.)

A gallery of undecidable grammar questions

From that one bridge, a whole gallery of undecidable grammar problems falls out, each by a small tweak. First, ambiguity. A grammar is ambiguous if some string has two different parse trees. Take our two grammars T_top and T_bot, rename their start symbols, and glue them under one fresh start rule S -> S_top | S_bot. The combined grammar is ambiguous exactly when some string is generated by BOTH halves — which (by the bridge) happens exactly when the PCP instance has a match. So a decider for ambiguity would decide PCP. Conclusion: there is no algorithm that takes a context-free grammar and always tells you whether it is ambiguous. Parser-generator warnings about ambiguity are heuristics, never a complete check.

Next, universality and equivalence — and here is a lovely twist. You might guess we would test whether two grammars share a string, but it turns out to be easier to flip to COMPLEMENTS. For a single PCP instance one can build a grammar whose language is the COMPLEMENT of the set of valid matches (every string that is NOT a top-equals-bottom solution; this complement happens to be context-free even though the matches themselves need not be). That grammar generates EVERY string over its alphabet — i.e. it is universal, L(G) = Σ* — exactly when there is no match at all. So 'does this grammar generate all strings?' is undecidable. And once universality is undecidable, equivalence (do two grammars generate the same language?) is too: just ask whether your grammar is equivalent to a trivial fixed grammar that obviously generates Σ*. Same impossibility, borrowed in one line.

The line: which grammar questions stay decidable

It is tempting to walk away thinking 'everything about grammars is hopeless,' but that is false and the contrast is illuminating. Several basic grammar questions are perfectly decidable. Membership — 'does grammar G generate string w?' — is decidable: convert G to a normal form and run a parsing algorithm like CYK in O(n^3) time, where n is the length of w (the cube being a worst-case upper bound, not a promise of slowness on every input). Emptiness — 'does G generate ANY string at all?' — is decidable too: mark which nonterminals can eventually produce a string of terminals, propagate the marks bottom-up, and check whether the start symbol gets marked. Finiteness — 'is L(G) finite?' — is decidable by looking for a 'pumpable' cycle among the useful nonterminals. None of these touches PCP, so none of them is poisoned.

So what makes the difference between the decidable and the undecidable questions? Look closely: the decidable ones (membership, emptiness, finiteness) are about ONE grammar's language in isolation. The undecidable ones (equivalence, universality, ambiguity, shared-string) all secretly compare TWO languages, or ask the language to fill ALL of Σ* — and that is exactly the spot where the lack of closure under intersection and complement lets PCP smuggle itself in. As a sanity check, contrast the equivalence problem for DFAs, which you met earlier and which IS decidable: regular languages are closed under everything, you can minimize and compare, and a DFA is a finite, fully-mappable object. A grammar can encode arbitrary computation in a way a DFA cannot, and that extra power is precisely what costs you decidability.

Up the hierarchy: Turing-machine emptiness and equivalence

The same reduction muscle reaches one rung higher, to Turing machines, where things are even worse. For a Turing machine M, ask: 'is L(M) empty?' — does M accept nothing at all? This E_TM problem is undecidable, and the reduction is direct: from an instance of the acceptance problem A_TM ('does M accept w?'), build a machine that ignores its own input and simply simulates M on w, accepting if M does. That built machine has an empty language exactly when M does NOT accept w. A decider for emptiness would therefore decide A_TM — which we already proved impossible. And TM equivalence ('do M1 and M2 accept the same language?') is at least as hard: compare any M against a fixed machine that accepts nothing, and equivalence collapses into the emptiness question.

There is a further sting worth naming honestly. TM emptiness is not just undecidable, it is not even recognizable — and its sibling, the equivalence problem, is even harder, sitting beyond both the recognizable and co-recognizable classes (a hint of the infinite ladder of unsolvability above mere undecidability). 'Undecidable' is not the bottom of a one-rung basement; it is the floor of a whole tower. Mapping reductions, the tool from guide 2, transfer not just undecidability but hardness in general, and that is why a single source problem like PCP or A_TM can topple so many targets. The mechanism never changes — only the costume of the target problem does, with the direction always pointing from the known-hard source down to your new target.

  1. Pick a target question you suspect is undecidable (e.g. 'is this grammar ambiguous?', 'is L(M) empty?').
  2. Choose a KNOWN-undecidable source — PCP for string/grammar puzzles, A_TM or the halting problem for machine behaviour.
  3. Build a computable translator: from any source instance, construct a target instance whose YES/NO answer matches the source's. (This building must itself always halt — it is just rewriting, never running the dangerous machine.)
  4. Conclude: a decider for the target would, via the translator, decide the source. The source has none, so the target has none. Done — no diagonalization needed.