Course contentsShow
← Computer Science
Lesson 1836 of 2,87241. Context-Free LanguagesFree lesson

Converting CFGs to PDAs

Algorithm for constructing a PDA from a given context-free grammar using stack to simulate derivations.

Converting CFGs to PDAs

What you'll learn: You'll master the algorithm that transforms any context-free grammar into an equivalent pushdown automaton that recognizes the same language.

The Core Idea

Remember that PDAs and CFGs are equivalent in power—they both define exactly the context-free languages. Converting a CFG to a PDA makes this connection concrete: the PDA essentially simulates leftmost derivations of the grammar using its stack.

The algorithm creates a PDA that:

  1. Pushes the start symbol onto the stack
  2. Repeatedly expands nonterminals using production rules
  3. Matches terminals with input symbols
  4. Accepts when both input and stack are empty

The Construction Algorithm

Given a CFG G = (V, Σ, R, S), construct PDA P:

States: Three states: q_start, q_loop, q_accept

Stack alphabet: All grammar symbols (terminals and nonterminals)

Transitions:

  • Initialize: From q_start to q_loop, push start symbol S (ε-transition)
  • Expand nonterminals: In q_loop, for each production A → w, pop A and push w in reverse order (ε-transition, no input consumed)
  • Match terminals: In q_loop, for each terminal a, pop a when reading a from input
  • Accept: From q_loop to q_accept when stack is empty (ε-transition)

Why It Works

Think of the stack as a to-do list for the derivation. When you pop a nonterminal, you're deciding "which production rule applies here?" and pushing the right-hand side tells the PDA what to derive next. When you pop a terminal, you verify it matches the input—like checking your work against the string being parsed.

Key Takeaway: Any CFG can be mechanically converted to a PDA that uses its stack to maintain the current sentential form during a leftmost derivation, popping nonterminals to expand them and matching terminals against the input.