Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 59 · Pushdown Automata

PDA Acceptance and Equivalence with CFGs

Compare PDA acceptance by final state and by empty stack, convert between them, and turn any context-free grammar into an equivalent PDA in Python.

The previous lesson mentioned two ways for a PDA to accept: by final state and by empty stack. This lesson shows they are interchangeable, and then proves the central theorem of the chapter: a language is context-free if and only if some PDA recognizes it. We will build the grammar-to-PDA direction as running code.

Acceptance by final state

L(M) is the set of strings w for which the PDA can reach a configuration (f, ε, γ) with f ∈ F, after reading all of w. The stack may hold anything. This is the style of our a^n b^n machine: its last move ε, $ / $ goes to the accepting state when $ is on top.

Acceptance by empty stack

N(M) is the set of strings w for which the PDA can reach (q, ε, ε): the whole input is read and the stack is empty, in any state. There are no accepting states at all; the set F is ignored. A PDA with an empty stack cannot move, so acceptance is the moment the stack runs dry.

The two languages L(M) and N(M) of the same machine are generally different. What is true is that for every language, there are machines of both kinds.

Converting between the two styles

Final state to empty stack. Given M accepting by final state, build M':

  1. Add a new bottom symbol # and a new start state that pushes $# and enters the old start state. The # guards against M accidentally emptying its stack and getting stuck.
  2. From every old accepting state add ε-moves into a new state pe.
  3. In pe, keep popping with ε-moves until the stack, # included, is empty.

Empty stack to final state. Given M accepting by empty stack, add a new bottom marker # under the old one, and a transition from any state, reading ε with # on top, into a new accepting state pf. If M empties its own stack, # becomes visible and M' accepts.

We can check the first construction in code. We convert the a^n b^n machine and compare it to the original on every string up to length 8.

Python Final-state to empty-stack conversion

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both lists are empty: the new machine agrees with the specification on all 511 strings tested. Because the old machine's $ marker lives above the new #, popping $ and # takes only ε-moves after a final state is reached.

From a grammar to a PDA

Now the key theorem. Given a context-free grammar G, we can build a PDA whose single state simulates a leftmost derivation:

  • Start with the grammar's start symbol S as the only symbol on the stack.
  • If a variable A is on top, nondeterministically replace it with the body of any rule A → α. (ε-move, push α.)
  • If a terminal a is on top and the next input is a, pop it and consume the input.
  • Accept by empty stack: the whole derivation has been matched against the input.
flowchart LR
    Q(("q")) -->|"ε, A / α   for each rule A → α"| Q
    Q -->|"a, a / ε   for each terminal a"| Q

One state, two kinds of loops. The stack holds the not-yet-matched part of the sentential form.

The code below turns a grammar given as a dictionary into rules for our simulator, using uppercase letters as variables. The grammar S → (S)S | ε generates exactly the balanced parentheses.

Python CFG to PDA for balanced parentheses

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The set of mistakes is empty for all strings up to length 10. Notice that the machine has only one state, which shows that the states of a PDA add nothing beyond what the stack can do, as long as you accept by empty stack.

From a PDA to a grammar

The reverse direction is the harder half of the theorem, so here is the idea without the full proof. Normalize the PDA so that it has one accepting state, empties its stack before accepting, and every move either pushes one symbol or pops one. Then create a variable [p X q] meaning:

"Starting in state p with X on top, the PDA can reach state q, having popped X and nothing below it, while reading exactly the string derived from [p X q]."

A pop-move δ(p, a, X) ∋ (q, ε) gives the rule [p X q] → a. A push-move δ(p, a, X) ∋ (r, YZ) gives rules [p X s] → a [r Y t] [t Z s] for all states t and s. The start variable derives all strings that take the machine from q0 with Z0 to an empty stack. The grammar can be large, but it is finite, and it proves every PDA language is context-free.

Together: CFG ⇒ PDA (our code) and PDA ⇒ CFG (the triple construction) show that the class of languages accepted by PDAs equals the class of context-free languages.

Why nondeterminism matters

The grammar-based PDA guesses which rule to apply. For S → aSb | ab it must decide whether the next a starts the last pair, and it cannot know. A deterministic version needs lookahead the PDA does not have. This is the first hint that deterministic and nondeterministic PDAs differ in power, which we explore in the next lesson.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. For a PDA that accepts by empty stack, what is the role of the set of final states F?

    In empty-stack acceptance, final states play no role. Only the empty stack with the input fully consumed counts.
  2. 2. In the CFG-to-PDA construction, what does the PDA do when a terminal a is on top and the next input symbol is a?

    Terminal matching: the guess made earlier must agree with the real input, so we pop the terminal and move the input head.
  3. 3. Why does the final-state to empty-stack conversion add a new bottom symbol #?

    Without a guard, the original machine might empty its stack in the middle of a run; the extra # keeps the stack nonempty until we decide to drain it.
  4. 4. What does the theorem proved in this lesson state?

    CFG to PDA and PDA to CFG constructions together show the two models define the same class of languages.

Summary

  • Acceptance by final state and by empty stack are equivalent in power; each can be converted into the other with a new bottom marker.
  • A CFG becomes a one-state PDA that simulates leftmost derivations: expand variables with ε-moves, match terminals with input.
  • A PDA becomes a CFG using variables [p X q] that describe "go from p to q, popping X".
  • Therefore PDA languages = context-free languages.

Next: DPDA vs NPDA