← 🥞 Pushdown Automata
Subtopic 2 of 4

4.2PDA ⇔ CFG

The idea

PDAs and CFGs are equivalent: a language is context-free exactly when some PDA accepts it.

Think of it like this: A grammar says how to build; a PDA says how to check. They describe the same thing.

Why it exists

It gives two ways to show a language is context-free.

How it works

  1. CFG → PDA: keep the sentential form on the stack; replace a variable by a rule's right side; match a terminal with the input.
  2. Only one state is needed.
  3. PDA → CFG: variables [p X q] meaning "go from state p to q popping X".
  4. Hence CFL = language of a PDA.

Worked example: S → aSb | ab on aabb

Stack S → aSb → (match a) Sb → ab·b → match a, b, b → empty. The PDA guesses the right rule each time.

Now play with it

  • →Step through the flow and watch the stack evolve.
Remaining inputaabb
Stack (top left)S
Actionstart
  • Top is S (a variable): replace by aSb (rule S → aSb)
  • Top is a (terminal) = next input a: pop and consume
  • Top is S: replace by ab (rule S → ab)
  • Match a
  • Match b
  • Match b: input and stack are both empty → ACCEPT

CFG S → aSb | ab, input aabb. One-state PDA accepting by empty stack: a variable on top is replaced by a rule's right side, a terminal on top is matched with the input.

Check yourself

A CFG with 3 variables and 2 terminals converts to a PDA with how many states (empty-stack construction)?

Remember: CFG → PDA: expand variables on the stack, match terminals with input.
Exam notes (the dense version)

A language is context-free iff some NPDA accepts it. From a CFG: a PDA with one state that, with a variable on top, replaces it by the right side of a rule, and with a terminal on top, matches it with the input.

Previous year questions: Pushdown Automata (2)

PYQs are grouped by topic, so this is the full set for Pushdown Automata; try the ones that match this subtopic. Open all 2 on the topic page.