Context-Free Grammars & Pushdown Automata

Finite automata fail on nested structure because they cannot count. Adding one stack fixes exactly that gap, and the class of languages it unlocks is the context-free languages.

A stack is the right memory for nesting because nesting is last-in-first-out. The most recently opened bracket is the first that must close; the most recently entered function scope is the first that must exit. A stack's discipline matches that structure precisely, which is why one stack is enough and why a second would be too much.

So the diagnostic question shifts. For regular languages we asked how many situations must be distinguished. For context-free languages we ask: is the structure a single nesting, or does it require two independent counts?

Matching brackets is a single nesting, so it is context-free. Requiring equal numbers of as, bs and cs in that order needs two independent comparisons, and a single stack cannot hold both.

The second organising fact is that grammars and pushdown automata are equivalent, but only when the automaton is nondeterministic. Unlike the regular case, determinism genuinely costs power here, and the deterministic context-free languages form a strictly smaller class.

1. Context-Free Grammars

A grammar is a four-tuple: variables, terminals, productions and a start symbol.

Every production has a single variable on its left-hand side, which is what "context-free" means: a variable may be replaced regardless of what surrounds it.

A derivation replaces variables one at a time until only terminals remain. A leftmost derivation always expands the leftmost variable; a rightmost derivation the rightmost.

A parse tree records the structure of a derivation without recording the order. Every parse tree corresponds to exactly one leftmost derivation and one rightmost derivation, which is why parse trees rather than derivations are the right object for discussing structure.

The grammar $S\to aSb\mid ϵ$ generates $\{a^n{b}^n\}$, the standard non-regular language, in two productions. That compactness is the point: what a finite automaton cannot do at all, a grammar does trivially.

2. Ambiguity

A grammar is ambiguous if some string has two distinct parse trees. Equivalently, two distinct leftmost derivations.

The classic case is an expression grammar without precedence, such as $E\to E+E\mid E\times E\mid \text{id}$. The string $\text{id}+\text{id}\times \text{id}$ parses two ways, and the two trees mean different things.

Ambiguity is a property of the grammar, not the language. The same language usually has an unambiguous grammar, obtained by layering the productions so that precedence and associativity are forced by the structure.

$E\to E+T\mid T$, and $T\to T\times F\mid F$, and $F\to \text{id}$.

This grammar generates the same language with exactly one parse tree per string, and the layering encodes that multiplication binds tighter than addition.

Some languages are inherently ambiguous, meaning every grammar for them is ambiguous. The standard example is $\{a^i{b}^j{c}^k:i=j\text{ or }j=k\}$, where strings satisfying both conditions must be derivable in two structurally different ways.

Checking whether a grammar is ambiguous is undecidable, so no algorithm can settle the question in general — which is why parser generators report conflicts rather than proving ambiguity.

3. Pushdown Automata

A PDA is a finite automaton with a stack. A move depends on the current state, the input symbol, and the top stack symbol, and it may change the state and replace the stack top with a string of symbols.

The stack is unbounded but accessible only at the top, which is exactly the restriction that makes the class context-free rather than recursively enumerable.

Two acceptance conditions exist.

Acceptance by final state ends in a designated accepting state. Acceptance by empty stack ends with nothing on the stack.

For nondeterministic PDAs the two are equivalent: any language accepted one way is accepted the other, by a construction that adds a bottom marker and a cleanup state.

For deterministic PDAs they are not equivalent. Empty-stack acceptance forces the language to be prefix-free, since once the stack empties the machine cannot continue, so it accepts strictly fewer languages.

The central theorem is that nondeterministic PDAs and context-free grammars describe exactly the same languages. The construction from grammar to PDA keeps the current sentential form's tail on the stack and expands variables as they surface.

4. Determinism Costs Power

This is the sharpest contrast with the regular case, and it is examined directly.

For finite automata, nondeterminism adds no power. For pushdown automata, it does: the deterministic context-free languages are a strict subset of the context-free languages.

The witness is the language of even-length palindromes, $\{w{w}^R\}$.

A nondeterministic PDA pushes symbols, guesses the midpoint, and then pops while matching. If the guess is right, the stack empties exactly as the input ends.

A deterministic PDA cannot make that guess. Reading left to right it has no way to know where the middle is, and by the time it could tell, it has already pushed past the point where it needed to start popping.

Adding an explicit centre marker fixes it. The language $\{wc{w}^R\}$ is deterministic, because the marker announces the midpoint and no guess is needed.

That single character is the whole difference between the two classes, which is why the pair appears so often.

The closure table is the most examined content in the chapter, and the two surprises are worth stating plainly.

Context-free languages are not closed under intersection. The languages $\{a^n{b}^n{c}^m\}$ and $\{a^m{b}^n{c}^n\}$ are both context-free, but their intersection is $\{a^n{b}^n{c}^n\}$, which is not.

Deterministic context-free languages are closed under complement but not union, which is the exact reverse of the general case. Complement works because a deterministic machine has one computation path, so accepting states can be swapped — the same argument as for DFAs.

5. Normal Forms

Two normal forms restrict the shape of productions without changing the language.

Chomsky normal form allows only $A\to BC$ and $A\to a$, with a single exception for $S\to ϵ$ if the empty string is in the language.

Its value is structural: every parse tree becomes binary, so a string of length $n$ has a derivation of exactly $2n-1$ steps. That fixed length is what makes the CYK parsing algorithm possible, running in $O(n^3)$ time by filling a table over substrings.

Greibach normal form allows only $A\to a\alpha$, where $\alpha$ is a string of variables. Every production consumes exactly one terminal, so a derivation of a length-$n$ string takes exactly $n$ steps and left recursion is impossible by construction.

Converting to a normal form requires simplification first, and the order of the simplification steps matters.

Remove $ϵ$-productions, then unit productions, then useless symbols. Removing $ϵ$-productions can create new unit productions, and removing unit productions can create new useless symbols, so reversing the order leaves work undone.

A symbol is useless if it is either non-generating — it derives no terminal string — or unreachable from the start symbol. Both checks are needed, and non-generating symbols must be removed before unreachable ones, since removing a non-generating symbol can make others unreachable.

6. Decidable and Undecidable Questions

Some questions about context-free languages can be answered algorithmically and some cannot, and the boundary is examined.

The pattern is that questions about a single grammar's basic structure are decidable, while questions comparing grammars or characterising the language are not.

Equivalence is decidable for deterministic context-free languages, which is a deep result and a standard distractor: the general case is undecidable but the deterministic case is not.

7. Worked Examples

Example 1. Write a grammar for $\{a^n{b}^m:n\ge m\ge 0\}$ and derive $aaab$.

The condition is that there are at least as many $a$s as $b$s.

Split it into a matched core plus extra $a$s on the left.

$S\to aS\mid A$, and $A\to aAb\mid ϵ$.

$A$ generates exactly $a^k{b}^k$ for any $k\ge 0$, and $S$ prefixes any number of extra $a$s.

Derive $aaab$: $S\Rightarrow aS\Rightarrow aaS\Rightarrow aaA\Rightarrow aaaAb\Rightarrow aaaϵb=aaab$.

Here two extra $a$s came from $S$ and one matched pair from $A$, giving $n=3$ and $m=1$.

Checking the boundary cases confirms the grammar. With no $S$ recursion and no $A$ recursion the derivation is $S\Rightarrow A\Rightarrow ϵ$, giving the empty string with $n=m=0$. There is no way to produce more $b$s than $a$s, since every $b$ comes from an $A$ production that also produces an $a$.

Example 2. Show that $E\to E+E\mid E\times E\mid \text{id}$ is ambiguous, and give an unambiguous grammar for the same language.

The string $\text{id}+\text{id}\times \text{id}$ has two distinct parse trees.

Tree 1 applies $E\to E+E$ at the root, with the left child deriving $\text{id}$ and the right child deriving $\text{id}\times \text{id}$. This groups as $\text{id}+(\text{id}\times \text{id})$.

Tree 2 applies $E\to E\times E$ at the root, with the left child deriving $\text{id}+\text{id}$ and the right deriving $\text{id}$. This groups as $(\text{id}+\text{id})\times \text{id}$.

Two distinct trees for one string means the grammar is ambiguous. Note that the two trees also mean different things, which is why ambiguity matters for a compiler.

The unambiguous version layers the productions by precedence.

$E\to E+T\mid T$, and $T\to T\times F\mid F$, and $F\to \text{id}$.

Now $\text{id}+\text{id}\times \text{id}$ has exactly one tree. The root must be $E\to E+T$, because a $T$ cannot generate a top-level $+$; the $T$ on the right then generates $\text{id}\times \text{id}$.

The layering forces multiplication to bind tighter, and the left recursion in each layer forces left associativity. The language is unchanged.

Example 3. Design a PDA for $\{a^n{b}^n:n\ge 1\}$.

Use a stack to count.

Phase 1: in state $q_0$, on reading $a$ push a marker. Stay in $q_0$.

Phase 2: on reading the first $b$, move to $q_1$ and pop one marker.

Phase 3: in $q_1$, on reading $b$ pop one marker. Stay in $q_1$.

Acceptance: if the input ends in $q_1$ with the stack containing only the bottom marker, accept.

The transitions enforce the structure. Once in $q_1$ no $a$ is accepted, which rules out strings like $abab$. Popping fails if the stack runs out early, which rules out more $b$s than $a$s. Ending with markers remaining rules out more $a$s than $b$s.

This PDA is deterministic, because the switch from pushing to popping is triggered by the input symbol changing from $a$ to $b$, not by a guess. The language is therefore a deterministic context-free language.

Example 4. Why is $\{w{w}^R\}$ not deterministic while $\{wc{w}^R\}$ is?

For $\{wc{w}^R\}$, the centre marker $c$ appears exactly once and is not in the alphabet of $w$. The PDA pushes every symbol until it reads $c$, then switches to popping and matching.

The switch is triggered by an observable event, so no guess is needed and the machine is deterministic.

For $\{w{w}^R\}$ there is no marker. Reading left to right, the machine sees only symbols from the same alphabet and has no way to detect the midpoint.

A nondeterministic PDA handles it by guessing: at every position it may either continue pushing or switch to popping. If any guess is correct, the machine accepts, and exactly one guess is correct for a genuine palindrome.

A deterministic machine must commit. If it switches too early it will have symbols left over; too late and the stack empties prematurely. Since the correct switching point depends on the total length, which is not known until the input ends, no deterministic strategy exists.

The formal proof is harder than the intuition, but the intuition is what the exam tests: the missing marker is the entire difference, and it separates the two language classes.

Example 5. Show that context-free languages are not closed under intersection.

Take two languages.

$L_1=\{a^n{b}^n{c}^m:n,m\ge 0\}$ and $L_2=\{a^m{b}^n{c}^n:n,m\ge 0\}$.

Both are context-free. $L_1$ has grammar $S\to XY$, $X\to aXb\mid ϵ$, $Y\to cY\mid ϵ$, which matches $a$s against $b$s with a stack and appends unrestricted $c$s. $L_2$ is the mirror image.

Their intersection requires both conditions simultaneously: the $a$ and $b$ counts equal, and the $b$ and $c$ counts equal.

$L_1\cap L_2=\{a^n{b}^n{c}^n:n\ge 0\}$.

This language is not context-free, which is proved with the pumping lemma for context-free languages.

Intuitively, a single stack can hold one comparison. Matching $a$s against $b$s consumes the stack, leaving nothing to match the $c$s against.

So two context-free languages intersected can produce a non-context-free one, and the class is not closed under intersection.

The consequence for complement follows immediately. If the class were closed under complement, then since it is closed under union, De Morgan's law would give closure under intersection. It is not closed under intersection, so it cannot be closed under complement either.

Example 6. Simplify the grammar $S\to AB\mid a$, $A\to a$, $B\to BC$, $C\to Bc$, then explain why the order of steps matters.

There are no $ϵ$-productions and no unit productions, so start with useless symbols.

Step 1: find non-generating symbols. A symbol is generating if it can derive a string of terminals.

$A\to a$, so $A$ generates. $S\to a$, so $S$ generates.

$B\to BC$ requires both $B$ and $C$ to generate, and $C\to Bc$ requires $B$. Neither has any other production, so neither $B$ nor $C$ can ever produce a terminal string. Both are non-generating.

Remove $B$ and $C$, along with every production mentioning them. That deletes $S\to AB$, $B\to BC$ and $C\to Bc$.

The grammar becomes $S\to a$, $A\to a$.

Step 2: find unreachable symbols. From $S$ we can reach nothing but terminals, so $A$ is now unreachable.

Remove $A$. The final grammar is $S\to a$, generating the single string $a$.

The order matters because removing non-generating symbols made $A$ unreachable. Had unreachability been checked first, $A$ would have appeared reachable through $S\to AB$, and the second pass would have been needed anyway.

The general rule is that non-generating symbols are removed before unreachable ones, and both after $ϵ$-productions and unit productions, since each earlier step can create new instances of the later problems.

Summary

A stack is the memory nesting requires, because nesting is last-in-first-out. One stack gives the context-free languages; the diagnostic question is whether the structure is a single nesting or needs two independent counts.

A context-free grammar has a single variable on every left-hand side. Parse trees, not derivations, are the right object for structure, since each tree matches exactly one leftmost and one rightmost derivation.

Ambiguity means two parse trees for one string. It is a property of the grammar and is usually removable by layering for precedence, but some languages are inherently ambiguous, and testing ambiguity is undecidable.

A PDA is a finite automaton with a stack accessible only at the top. Final-state and empty-stack acceptance are equivalent for nondeterministic PDAs but not for deterministic ones, where empty-stack acceptance forces prefix-freeness.

Nondeterministic PDAs and context-free grammars are equivalent. Deterministic PDAs are strictly weaker, and $\{w{w}^R\}$ against $\{wc{w}^R\}$ is the witness: the centre marker removes the guess.

Context-free languages are closed under union, concatenation, star and intersection with a regular language, but not under intersection or complement. Deterministic context-free languages are closed under complement but not union — the exact reverse.

Chomsky normal form makes parse trees binary and enables CYK parsing at $O(n^3)$. Greibach normal form consumes one terminal per step and eliminates left recursion.

Simplify in order: $ϵ$-productions, then unit productions, then non-generating symbols, then unreachable ones, because each step can create instances of the next problem.

Membership, emptiness and finiteness are decidable; ambiguity, equivalence, regularity and universality are not — though equivalence is decidable for deterministic context-free languages.