PDA and CFG equivalence

Why it exists

Two very different descriptions, grammars (generate strings by rewriting) and pushdown automata (accept strings with a stack), define the same languages: the context-free languages. Each direction is a construction, and GATE asks for the sizes: the number of states, stack symbols and transitions of the PDA built from a grammar, and the number of variables of the grammar built from a PDA. The equivalence also lets us prove properties of CFLs with whichever description is more convenient.

Prerequisites

You need PDAs and their acceptance conditions (PDA) and grammars with derivations (context-free grammars); the Greibach variant uses normal forms.

Precise definitions

Theorem. A language is context-free iff some PDA accepts it (by empty stack, equivalently by final state).

From a grammar to a PDA

Given $G = (V, \Sigma, R, S)$, build the PDA with one state $q$, input alphabet $\Sigma$, stack alphabet $V \cup \Sigma$, initial stack content $S$ (the start variable alone), accepting by empty stack, and the transitions:

1. for every production $A \to \alpha$: $(q, \alpha) \in \delta(q, \varepsilon, A)$ (pop the variable, push the right side with its first symbol on top);
2. for every terminal $a$: $(q, \varepsilon) \in \delta(q, a, a)$ (match a terminal on top of the stack with the input and pop it).

Idea. The stack always holds the part of the current sentential form that has not been matched yet. The machine therefore follows a leftmost derivation: replace the leftmost variable (an $\varepsilon$-move that guesses a production), or match the leftmost terminal. The stack is empty and the input is used up exactly when the derivation has produced the input string.

Size. One state; $|V| + |\Sigma|$ stack symbols; $|R| + |\Sigma|$ transitions. A string of length $n$ whose leftmost derivation has $d$ steps is accepted by a computation of $d + n$ moves.

From a PDA to a grammar (the triple construction)

Given a PDA $P$ accepting by empty stack with start state $q_0$, bottom symbol $Z_0$, states $Q$ and stack alphabet $\Gamma$, build a grammar with the variables

$S \qquad \text{and} \qquad [p\,X\,q] \quad \text{for all } p, q \in Q,\ X \in \Gamma.$

Meaning. $[p\,X\,q]$ generates exactly the strings $w$ that the PDA can read while going from state $p$ to state $q$ and popping $X$ (and everything pushed above it later) for good, never touching what lies below $X$.

Productions:

• $S \to [q_0\,Z_0\,p]$ for every $p \in Q$ (the whole computation pops $Z_0$);
• for every transition $(r, Y_1 Y_2 \cdots Y_k) \in \delta(q, a, X)$ ($a \in \Sigma \cup \{\varepsilon\}$), and for every choice of states $r_1, \ldots, r_k$: $[q\,X\,r_k] \to a\,[r\,Y_1\,r_1]\,[r_1\,Y_2\,r_2] \cdots [r_{k-1}\,Y_k\,r_k];$ for $k = 0$ (a pop): $[q\,X\,r] \to a$.

Size. At most $|Q|^2 |\Gamma| + 1$ variables, and for a transition that pushes $k$ symbols, $|Q|^k$ productions. Most of them are useless (the chosen intermediate states never occur in a computation) and disappear when useless symbols are removed.

Grammar in Greibach normal form to a PDA without epsilon-moves

For a grammar in GNF ($A \to a\,\alpha$ with $\alpha$ a string of variables), use one state, stack alphabet $V$, initial stack $S$, accept by empty stack, and for every production $A \to a\alpha$ the transition $(q, \alpha) \in \delta(q, a, A)$. Every move reads an input symbol: no $\varepsilon$-moves, and a string of length $n$ is accepted in exactly $n$ moves (verified on seven grammars).

How it works

Example: the PDA built from $S \to aSb \mid \varepsilon$

Transitions: $\delta(q, \varepsilon, S) = \{(q, aSb), (q, \varepsilon)\}$, $\delta(q, a, a) = \{(q, \varepsilon)\}$, $\delta(q, b, b) = \{(q, \varepsilon)\}$: $4$ transitions $= 2$ productions $+ 2$ terminals. The computation on $aabb$ follows the leftmost derivation and builds its parse tree:

It takes $7$ moves: $3$ expansions ($S \to aSb$ twice and $S \to \varepsilon$) and $4$ matches. The same construction applied to the grammars of the previous pages gave PDAs that accept exactly the same languages (named grammars: $a^n b^n$, palindromes, balanced parentheses, equal counts; and $200$ random grammars).

Example: the grammar built from a PDA

Take the two-state PDA for $a^n b^n$ that accepts by empty stack: $\delta(q_0, a, Z) = \{(q_0, AZ)\}$, $\delta(q_0, a, A) = \{(q_0, AA)\}$, $\delta(q_0, b, A) = \{(q_1, \varepsilon)\}$, $\delta(q_1, b, A) = \{(q_1, \varepsilon)\}$, $\delta(q_0, \varepsilon, Z) = \{(q_1, \varepsilon)\}$, $\delta(q_1, \varepsilon, Z) = \{(q_1, \varepsilon)\}$. For each transition the table counts the productions the construction makes and lists the useful ones:

Overall: $9$ variables ($2^2 \cdot 2 + 1$) and $14$ productions are made; after removing the useless ones $5$ variables and $7$ productions remain:

$S \to [q_0 Z q_1], \quad [q_0 Z q_1] \to \varepsilon \mid a\,[q_0 A q_1]\,[q_1 Z q_1], \quad [q_0 A q_1] \to a\,[q_0 A q_1]\,[q_1 A q_1] \mid b, \quad [q_1 Z q_1] \to \varepsilon, \quad [q_1 A q_1] \to b.$

This is a (renamed) grammar for $\{a^n b^n\}$: $[q_1 A q_1] \to b$ and $[q_1 Z q_1] \to \varepsilon$ can be substituted, giving $[q_0 A q_1] \to a [q_0 A q_1] b \mid b$ ($a^k b^{k+1}$) and $[q_0 Z q_1] \to \varepsilon \mid a [q_0 A q_1]$ (that is $\varepsilon$ or $a^{k+1} b^{k+1}$). The language of this grammar equals that of the PDA on all strings up to length $10$.

Consequences

• Closure of CFLs under union, concatenation and star is easiest with grammars; closure under intersection with a regular language is easiest with PDAs (run the PDA and a DFA in parallel) (closure properties of CFLs).
• Acceptance by final state or by empty stack gives the same class of languages.
• Deterministic PDAs are strictly weaker than nondeterministic ones (textbook theorem, quoted; see the next batch); the grammar-to-PDA construction above is nondeterministic by nature (the production is guessed) (DPDA versus NPDA).

Worked examples

Cheat box

Traps and GATE patterns

Connections

The equivalence gives two ways to prove closure properties of CFLs (closure properties of CFLs); it also shows that deterministic parsing of programming languages needs a restricted kind of PDA (DPDA versus NPDA); the Greibach variant uses normal forms (normal forms).

PYQs

Self-check

Revision card

References