Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Equivalence of PDA and CFG

Equivalence theorem: a language is context-free iff some pushdown automaton recognizes it, with constructive conversions both ways (CFG → PDA and PDA → CFG).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Two or three sentences: where an engineer uses this.

Understanding the equivalence between context-free grammars (CFGs) and pushdown automata (PDAs) explains why many programming-language constructs (balanced parentheses, nested blocks, matched begin/end) are parseable. An engineer designing a compiler front-end or a parser generator uses these results to move between grammar specifications and automata-based recognizers.

Key ideas

Explain plainly and define terms before use.

  • Alphabet (Σ): a finite set of symbols called terminals. (Defined before use.)
  • String: finite sequence of symbols from an alphabet.
  • Language: a set of strings over an alphabet.
  • Context-free grammar (CFG): a 4-tuple G = (V, Σ, R, S) where V is a finite set of nonterminal symbols, Σ is the terminal alphabet (V ∩ Σ = ∅), R is a finite set of productions of the form A → α with A ∈ V and α ∈ (V ∪ Σ), and S ∈ V is the start symbol. The grammar generates a string when S ⇒ w (derivation); the set of all generated terminal strings is L(G).
  • Pushdown automaton (PDA): a 7-tuple M = (Q, Σ, Γ, δ, q0, Z0, F) where Q is a finite set of states, Σ the input alphabet, Γ the stack alphabet, δ the transition relation (possibly nondeterministic) δ ⊆ Q × (Σ ∪ {ε}) × Γ × Q × Γ*, q0 ∈ Q the start state, Z0 ∈ Γ the initial stack symbol, and F ⊆ Q the accepting states. The PDA recognizes a string if there exists a valid sequence of transitions that consumes the input and meets the acceptance condition.
  • Acceptance modes: PDAs can accept by empty stack (stack becomes empty after consuming the input) or by final state (machine reaches a state in F after consuming input). These modes are equivalent: for any PDA in one mode you can construct a PDA in the other mode that recognizes the same language.

Main theorem (exact statement universities expect):

  • The class of context-free languages (CFLs) is exactly the class of languages generated by CFGs and also exactly the class of languages recognized by PDAs.

Formally:

  • For any CFG G there exists a PDA M such that L(G) = L(M).
  • For any PDA M there exists a CFG G such that L(M) = L(G).

Both directions are constructive; below are the common constructions asked for in exams.

Construction 1 — CFG → PDA (standard leftmost-derivation simulation, accept by empty stack):

  • Given G = (V, Σ, R, S), build M = ({q}, Σ, Γ, δ, q, Z0, ∅) where Γ = V ∪ Σ ∪ {Z0}. Start stack symbol Z0.
  • Initialise by pushing S: include transition (q, ε, Z0) → (q, S Z0). (If your model allows a separate start move, you can instead initially push S.)
  • For each production A → X1 X2 ... Xk (Xi ∈ V ∪ Σ, k ≥ 0 with k = 0 meaning ε), add transition (q, ε, A) → (q, X1 X2 ... Xk). This replaces nonterminal A on top of stack by the production body; this simulates a leftmost derivation step on the stack.
  • For each terminal a ∈ Σ, add transition (q, a, a) → (q, ε). This matches the input symbol a with the same terminal on top of stack and pops it.
  • Accept by empty stack: add (q, ε, Z0) → (q, ε). Thus when input is consumed and only Z0 remains, pop Z0 by ε so the stack is empty and accept.

Sketch of correctness: the stack holds the remaining sentential form (top is leftmost symbol). ε-transitions apply productions; terminal matches consume input. A leftmost derivation in G corresponds to a run of M and vice versa.

Construction 2 — PDA → CFG (standard A_pq variables):

  • For a PDA M = (Q, Σ, Γ, δ, q0, Z0, F) we first convert to an equivalent PDA that accepts by empty stack (if original accepts by final state). This is routine: add a new bottom symbol and transitions to clear stack on reaching a final state.
  • Define a grammar G with variables A_{pq} for every pair p, q ∈ Q. Intuition: A_{pq} generates all strings w that can take M from state p with empty stack to state q with empty stack (i.e., starting and ending with an empty stack). For acceptance by empty stack, take S to have productions S → A_{q0 q} for all q ∈ Q (the stack may empty in any state); if you instead keep final‑state acceptance, use S → A_{q0 qf} for each qf ∈ F.
  • Productions are added as follows (standard, exam‑expected scheme; first convert M to the normal form where each move does exactly one of: read one input symbol without changing the stack, push one stack symbol, or pop one stack symbol, and M accepts by empty stack):
    • For every p ∈ Q, include A_{pp} → ε. (Empty path.)
    • For all p,q,r ∈ Q, include A_{pq} → A_{pr} A_{rq}. (Concatenation of empty‑stack paths.)
    • For each read move (u, a, X) → (v, X), add A_{uv} → a. (Read a with stack unchanged.)
    • For each push/pop pair on the same stack symbol X ∈ Γ, i.e., a push (p, ε, Y) → (r, X Y) and a matching pop (s, ε, X) → (q, ε), add A_{pq} → A_{rs}. (The substring read while X is on the stack is generated by A_{rs}.) These rules are finite and yield a grammar where A_{pq} generates exactly the strings that take M from p with empty stack to q with empty stack. See your course text for the full mechanical details.

This second construction is the most technical part the examiner expects you to describe and often to outline with the clear definition that A_{pq} generates strings that cause M to go from p (empty stack) to q (empty stack). The complete formal derivation is mechanical but long; many exam answers give the definition of A_{pq}, the base A_{pp} → ε, and show how to create productions for push/pop transitions with an example.

Important assumptions and notes universities expect:

  • The PDA is allowed to be nondeterministic. Deterministic PDAs are strictly weaker than nondeterministic PDAs in language power.
  • You may assume acceptance by empty stack or show conversion from final-state acceptance; state the choice and show the small conversion.

Diagrams to draw (exactly what to label):

  • For CFG → PDA: draw one state q, input tape arrow left→right, and a stack box showing initial Z0 then S being pushed. Draw sample transitions as labelled arrows: (ε, A → RHS) and (a, a → ε). Label transitions exactly as (current-state, input-symbol-or-ε, stack-top) → (next-state, replacement-on-stack).
  • For PDA → CFG: draw small PDA that pushes A then later pops A across input a...b to illustrate how A_{pq} is created. Label states p,q and the push and pop transitions with stack symbol and input symbol.

I am reasonably sure about the CFG → PDA construction and the definition of variables A_{pq} for PDA → CFG. The exact mechanical listing of all productions in PDA → CFG is lengthy; check your course text for the fully formal form if the examiner demands every production written explicitly.

Formulas

G = (V, Σ, R, S) — CFG with nonterminals V, terminals Σ, productions R, start S. (No SI units.)

M = (Q, Σ, Γ, δ, q0, Z0, F) — PDA with states Q, input alphabet Σ, stack alphabet Γ, transition relation δ, start state q0, initial stack symbol Z0, accepting states F.

Transition notation: (p, a, X) → (q, γ) means when in state p, reading input symbol a (a may be ε), with X on top of stack, PDA moves to state q and replaces X by string γ (γ ∈ Γ*).

Variable meaning in PDA→CFG: A_{pq} — generates strings w such that M can go from state p with an empty stack to state q with an empty stack while reading w.

Worked examples

Example 1 (CFG → PDA). Convert G: S → a S b | ε into a PDA M.

  1. G = (V={S}, Σ={a,b}, R={S→a S b, S→ε}, S).
  2. Build M with single state q and initial stack Z0. Push S initially: (q, ε, Z0) → (q, S Z0).
  3. For production S → a S b add (q, ε, S) → (q, a S b).
  4. For S → ε add (q, ε, S) → (q, ε).
  5. For terminals add (q, a, a) → (q, ε) and (q, b, b) → (q, ε).

Trace input "a a b b" ("aabb"):

  • Start with input aabb, stack Z0. Apply push S: stack S Z0.
  • Apply (ε, S→a S b): stack a S b Z0.
  • Top is terminal a; match input a with (a, a → ε): consume first a; stack S b Z0; remaining input abb.
  • Apply (ε, S→a S b) again: stack a S b b Z0.
  • Match a with (a, a → ε): consume second a; stack S b b Z0; remaining input bb.
  • Apply (ε, S→ε): stack b b Z0.
  • Match b with (b, b → ε): consume first b; stack b Z0; remaining input b.
  • Match b with (b, b → ε): consume last b; stack Z0; input empty.
  • Pop bottom symbol with (ε, Z0 → ε) and accept by empty stack.

Final answer: M recognizes {a^n b^n}.

Example 2 (PDA → CFG). Start from a PDA M for {a^n b^n}:

  • States {q}, stack alphabet {Z0, X}, transitions: (q, a, Z0) → (q, X Z0) and (q, a, X) → (q, X X) to push X on reading a; (q, b, X) → (q, ε) to pop X when reading b; (q, ε, Z0) → (q, ε) to allow acceptance of ε by emptying the stack; accept by empty stack.

Construct variables A_{qq}. Base: A_{qq} → ε. From transitions push X on a and later pop X on b we get production leading to A_{qq} → a A_{qq} b A_{qq} which collapses to S → a S b | ε after removing redundant variables. Thus grammar is S → a S b | ε which generates {a^n b^n}.

(Notes: the full PDA→CFG mechanically produces many A_{pq} variables; for this one-state PDA it simplifies to the standard grammar.)

Common mistakes

  • In PDA→CFG, defining variables incorrectly (confusing what A_{pq} represents), or missing base productions A_{pp} → ε.
  • Not handling ε-productions carefully: forgetting that A → ε may be required for empty paths.
  • Trying to use deterministic PDA when language needs nondeterminism (forgetting that PDA may be nondeterministic).

For your exam

Kinds of questions: definitions (define CFG, PDA, acceptance modes), short notes (state and explain theorem), derivation/conversion problems (convert given CFG to PDA or PDA to CFG), diagrams (draw PDA with labelled transitions), proofs (show CFG→PDA correctness or sketch PDA→CFG construction), and worked examples (convert {a^n b^n} or more complex grammars).

What full-marks answer includes:

  • Precise definitions of CFG and PDA and clear statement of acceptance mode used.
  • Exact construction steps with transition rules written in the standard notation (p, a, X) → (q, γ).
  • A small worked trace showing correspondence (for CFG→PDA include a derivation and matching PDA run; for PDA→CFG include how A_{pq} generates strings and base productions).
  • A correctness argument (sketch is acceptable if full formal proof is long): show one-to-one correspondence between derivations and PDA runs.

Quick check

  1. What does variable A_{pq} mean in the PDA→CFG construction?
  2. Give the PDA transition you add for a CFG production A → X1 X2.
  3. Why are acceptance-by-empty-stack and acceptance-by-final-state equivalent for PDAs?

Answers: 1) Strings that take PDA from state p (empty stack) to state q (empty stack). 2) (q, ε, A) → (q, X1 X2). 3) You can convert one mode to the other by adding new start/accept states and extra stack-symbol and ε-transitions to clear or detect empty stack; this construction preserves recognized language.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?