Motivation
A context-free grammar can be tested for emptiness by marking productive variables. It is natural to ask whether it generates every word over its terminal alphabet, or whether two such grammars generate the same language. These questions have very different answers. We will reduce Post correspondence to grammar universality and make the direction of the reduction explicit.
The construction uses a delimiter and a reversed list of tile indices. A pushdown machine can compare a word with the concatenation specified by those indices, working from right to left. More subtly, it can accept every malformed or mismatching string. The union of two such mismatch languages is universal exactly when there is no correspondence match.
Definitions and prerequisites
Definition 5.5.1
(Post correspondence instance and solution)
A Post correspondence instance has finitely many tiles , , whose top and bottom words are nonempty over a finite alphabet . A solution is a nonempty sequence such that . The companion undecidability chapter proves that deciding existence of a solution remains impossible under this nonempty-word convention.
Definition 5.5.2
(Encoded match languages)
Let be a disjoint alphabet of index symbols, let be a fresh delimiter, and put . Define
The index symbols are terminals, even if their displayed names look like integers. The alphabets are disjoint, so a string has an unambiguous delimiter position and index suffix when it has the intended syntax.
Theorem 5.5.3
(Undecidability of universality)
There is no algorithm that, given a context-free grammar over its stated finite terminal alphabet, decides whether its language is the whole set of words over that alphabet.
Theorem 5.5.4
(Effective mismatch languages)
From the tiles one can effectively construct context-free grammars for and . Consequently one can construct a grammar for .
We use the companion effective pushdown-to-grammar construction and context-free closure under union. We give the mismatch pushdown machine explicitly enough to prove its behavior; no general closure of context-free languages under complement is assumed.
A stack machine for a mismatch
We now prove the effective mismatch languages theorem.
Proof
(A deterministic stack machine for the mismatch language)
For the top words , build a deterministic pushdown machine with a permanent bottom marker. Before reading a delimiter, it pushes every symbol from onto the stack. This prefix mode is accepting when the input ends: a string with no delimiter is not in . An index symbol or any other syntax violation in this mode moves to an accepting sink that consumes the rest of the input.
On the first , move to a ready state that is also accepting if input ends: no index has yet appeared, whereas requires at least one. Reading an index starts a finite sequence of -moves that compares in reverse order with the stack top. The finite control stores the current position in the fixed word . For each expected symbol, pop a matching stack symbol; on a mismatch or the bottom marker reached too soon, move to an accepting sink. Each tile word is finite, so this comparison phase always finishes.
After a successful comparison, an -check of the stack chooses one of two ready states. If the bottom marker is exposed, the just-read index suffix describes exactly the pushed word so far; this ready state is rejecting when the input ends. Any further index leads to an accepting sink, because every tile word is nonempty and no stack symbol remains. If the bottom marker is not exposed, the ready state is accepting when the input ends, because some unmatched prefix remains. It can read another index and begin its next finite comparison phase. A delimiter or a symbol in the index suffix is malformed and leads to an accepting sink.
All transient comparison and stack-check states are nonaccepting. This matters when the final input symbol has just been consumed: acceptance is determined after the bounded -phase settles, not by an intermediate state. Each ready state has only input-consuming moves, and each transient state has only its specified -move for the current stack symbol, so there is no nondeterministic choice or conflicting transition. Acceptance means reaching an accepting state after all input has been consumed, as usual.
If the input has intended syntax and equals an element of , every comparison matches and the stack becomes empty exactly after the last index, placing the machine in the rejecting ready state. If a letter differs, the stack is too short, the stack is too long at input end, or more index symbols arrive after exact exhaustion, the machine accepts. Missing delimiters, missing indices and malformed symbols are also accepted. Thus it accepts exactly .
The same construction with accepts . It is an effective finite pushdown machine: its comparison states are determined by the finite tile words. The companion construction converts it to a context-free grammar. Add a fresh union start to combine the two grammars, yielding a grammar for
Proof X-ray
Compare the concatenation from the right
The first index after the delimiter is , so the machine pops in reverse. It then pops in reverse, and so on. Exact exhaustion after a nonempty index suffix is equivalent to the original left-to-right prefix being . The one hypothesis used silently is that every tile word is nonempty: once the stack shows only the bottom marker, any further index must try to pop a symbol that is not there, so it can only lead to the accepting sink and never to a second rejecting configuration.
Reduction from correspondence
The universality theorem follows from this reduction.
Proof
(Reduction from Post correspondence)
If the Post instance has a solution , its common word followed by lies in both and . It is missing from , so is not universal. Conversely, a string in has the same explicit reversed index suffix on both sides. Reversing that suffix determines the same nonempty index sequence, and equality of the prefixes is a Post solution. Thus
The construction is effective and finite. If a universality decider existed, apply it to and reverse its yes/no answer to decide whether the Post instance has a solution. This contradicts the stated undecidability prerequisite. The reversal of the answer is harmless for a decision reduction, but it must be stated: a match makes the grammar nonuniversal.
Inclusion and equivalence consequences
Corollary 5.5.5
(Undecidability of inclusion and equivalence)
There is no algorithm that, given two context-free grammars over the same terminal alphabet, decides whether the language of the first is included in the language of the second, and there is none that decides whether the two languages are equal. Both problems stay undecidable when one of the grammars is required to generate every word over the alphabet.
Proof
(Reducing universality to inclusion and equivalence)
A grammar for can be constructed effectively, for example with a start rule that either stops or emits one terminal followed by the start. If inclusion of one context-free grammar language in another were decidable, testing would decide universality. Likewise, equivalence of two context-free grammars would decide whether . Therefore general context-free grammar inclusion and equivalence are undecidable.
The first argument uses a regular language on the left of the inclusion. It does not imply that inclusion in the opposite direction, with an arbitrary context-free language on the left and a regular language on the right, is undecidable. That latter problem can be handled using regular complementation and context-free intersection with a regular language, together with context-free emptiness.
Worked examples
Worked example 5.5.6
(A matching single tile)
Take one tile . The word belongs to both and , so it is excluded from the constructed union of mismatch languages. The grammar is not universal, matching the existence of the one-tile solution.
Worked example 5.5.7
(A mismatch on one side)
For the single tile , the string belongs to but not . The bottom mismatch machine accepts it, so the union grammar includes it. This string does not witness nonuniversality.
Worked example 5.5.8
(Reversed index order)
Suppose top words are and . The index sequence gives . After pushing , the machine reads and pops , then reads and pops followed by . The stack empties exactly at the end.
Worked example 5.5.9
(An incomplete prefix)
With one top tile , the string leaves one on the stack after the single index. It is not in , and the nonbottom ready state accepts the mismatch at input end. By contrast, finishes with the bottom marker and is rejected by that mismatch machine.
Common mistakes
Counterexample mode
Complement does not preserve context-free languages
One might argue that the complement of a context-free language is context-free, so a grammar for can simply be complemented. This is false in general. Over take the context-free languages and . A word lies in both exactly when and , so , which the pumping lemma for context-free languages shows is not context-free. If complement preserved context-freeness, then since union does, (complements taken in ) would be context-free, a contradiction. The proof here therefore builds special mismatch machines for these particular encoded languages, and applies union only after both mismatch languages are known to be context-free.
Common mistake
(Reading the index suffix in the original order)
The index suffix must be reversed. A stack exposes the last pushed symbol first, so its first post-delimiter comparison must be with the final tile's word in reverse. Reading the indices in the original order would generally compare the wrong tile with the end of the prefix.
Common mistake
(Letting a transient state decide acceptance)
A final state reached while input remains unread does not by itself accept under the stated convention. This is why an accepting ready state with unmatched stack symbols can later read another index and possibly move to the rejecting exact-match state. Conversely, transient -comparison states must not accidentally accept a valid string before comparison finishes.
Reading the two inclusion directions
The undecidable direction is whether a regular language can be included in a context-free language: universality asks whether every word of lies in the grammar's language. The opposite direction has a different structure. If is regular and is context-free, then exactly when is empty. A finite automaton can be complemented after determinization; its product with a pushdown machine is again a pushdown machine. The resulting context-free emptiness question is decidable by the companion productivity construction.
This comparison illustrates why a reduction should specify the order of its inputs. Writing only “inclusion is undecidable” hides a useful asymmetry and can lead a reader to infer that every restricted inclusion problem is hard. The proof above establishes undecidability for general grammar inclusion and even when the left side is the fixed regular language over the instance alphabet.
The finite-control implementation does not need to store a tile word on the stack. Each tile belongs to the fixed input instance used to construct the machine, so its symbols and the current position can be encoded in finitely many states. The stack stores the arbitrary-length word prefix. This separation is what makes the construction effective while allowing the input word to have unbounded length. A tile may contain several letters, but its comparison phase has a fixed finite maximum length. Thus it cannot remain forever in an -only phase after consuming the final index; it either detects a mismatch or reaches one of the two ready states.
Summary
An encoded Post solution is exactly a word in . Specialized stack machines recognize the complements of those two languages by comparing the reversed index suffix against the pushed prefix. Their union is universal exactly when no match exists. A universality decider would therefore decide Post correspondence, and general inclusion and equivalence inherit the impossibility.
Exercises
Quick check
(For top tiles , , what encoded string corresponds to the index sequence ?)
Concatenate the top words in the order of the indices, then write the indices in the opposite order.
Solution · Answer
The concatenated top word is and the reversed index suffix is , giving .
Quick check
(Why is required to be a fresh symbol outside both the word and index alphabets?)
Ask where the word part ends and the index part begins in an encoded string.
Solution · Answer
It marks the unique boundary between the word prefix and index suffix. Disjoint alphabets make the decoding used in both directions of the reduction unambiguous.
Quick check
(If the Post instance has a solution, is the constructed union grammar universal or nonuniversal? Explain.)
Locate the common word followed by its reversed index sequence relative to , and the grammar's language.
Solution · Answer
Nonuniversal. The common word followed by its reversed nonempty index sequence lies in both encoded languages and therefore outside their complement union.
Quick check
(How would a grammar-equivalence decider decide universality over ?)
Which fixed grammar should be compared with the input grammar?
Solution · Answer
Construct a grammar for and test whether it is equivalent to the input grammar. Equality holds exactly in the universal case.