Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 39

CFG to PDA Conversion

Recommended resources

Hello! Welcome to the next lesson in our exploration of the Theory of Computation.

In our last session, we established that Pushdown Automata can accept languages either by reaching a final state or by emptying their stack, and we proved that these two methods are equivalent in power. This was a crucial step in understanding the robustness of the PDA model.

Today, we will build a fundamental bridge between the generative world of grammars and the recognition world of automata. This lesson's objective is to master the algorithm to convert any given Context-Free Grammar (CFG) into an equivalent Pushdown Automaton (PDA). This process proves that for every context-free language, there exists a PDA that recognizes it.

This conversion is a beautiful piece of theory that has practical parallels. Your experience in building systems that translate specifications from one form to another—like a compiler converting source code (a grammar-like structure) into machine-executable instructions (an automaton-like process)—will provide a solid conceptual foundation for understanding today's topic.

1. The Core Idea: Simulating a Derivation

A Context-Free Grammar generates a string by starting with the start symbol and successively applying production rules. A PDA, on the other hand, recognizes a string by processing it from left to right. How can we make a PDA mimic the behavior of a CFG?

The core idea is to design a PDA that simulates a leftmost derivation of the input string.

  • The PDA will use its stack to store a "to-do" list of variables and terminals that it expects to see.
  • It starts by putting the grammar's start symbol on the stack.
  • At each step, it looks at the top of the stack:
    1. If the top is a terminal symbol, it must match the next symbol in the input string. If it matches, the PDA pops the symbol from the stack and consumes the input symbol.
    2. If the top is a variable, the PDA non-deterministically chooses one of that variable's production rules and replaces the variable on the stack with the right-hand side of that rule.

This process continues until both the input string has been fully consumed and the stack is empty. If this is possible, the string is accepted.

The following video segment introduces this concept and highlights a key challenge: a PDA can only access the top of its stack. This limitation naturally forces the simulation to follow a leftmost derivation.

4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion

Let's start by watching this segment from an MIT OpenCourseWare lecture. Professor Sipser explains the intuition behind converting a CFG to a PDA, including the idea of guessing substitutions and using the stack to keep track of the intermediate string.

Watch from 51:06 to 58:25. Pay close attention to the problem he describes as 'cheating' (accessing deep within the stack) and the elegant solution: only ever substitute variables when they appear at the top.

As the video explains, the PDA will systematically work on the leftmost non-terminal of the "sentential form" (the intermediate string of terminals and variables) stored on the stack.

2. The General Conversion Algorithm

Now, let's formalize this intuitive idea into a concrete algorithm that can convert any CFG into an equivalent PDA. We can construct a simple and elegant PDA that has just a few states. For a given CFG , we construct a PDA that accepts the language .

The construction is most cleanly described using a PDA that accepts by empty stack, which we know from the previous lesson is equivalent to acceptance by final state.

The PDA will have three main types of transitions:

  1. Initialization:

    • Start with a special bottom-of-stack marker, let's call it $.
    • Push the grammar's start symbol S onto the stack.

  2. Processing (Loop):

    • Rule (a) - Match a Terminal: If the symbol at the top of the stack is a terminal t, read the next input symbol. If they match, pop t from the stack.
    • Rule (b) - Expand a Variable: If the symbol at the top of the stack is a variable A, pop A and push the right-hand side of one of its production rules, A -> w. Crucially, you must push w onto the stack in reverse order. This ensures that the leftmost symbol of w ends up on top of the stack, ready to be processed next. This is a non-deterministic choice.

  3. Acceptance:

    • When the input is fully read and the only symbol left on the stack is the initial marker $, a final transition pops $ to empty the stack and accept the string.

The following resource provides a clear diagram of this generalized "shortcut" construction.

Lecture 8: L(CFG) = L(PDA)

This document from Georgia Tech provides a concise, formalized version of this conversion algorithm, often using a three-state model.

Please read section 1.1, 'CFG to PDA conversion' (page 1). Focus on the diagram showing the three states (q0, q1, q2) and the three types of transitions described. Note how it maps directly to our algorithm: initialization (ε, ε → S$), matching terminals (a, a → ε), and expanding variables (ε, A → w).

Example: CFG to PDA Conversion
This image illustrates the core components of the algorithm: the grammar's rules are converted into PDA transitions that either expand variables or match terminals.

Why push the RHS in reverse?

Let's say we have a rule A -> xyz. The PDA pops A. To simulate the derivation, it needs to process x, then y, then z. Since a stack is a Last-In, First-Out (LIFO) structure, to get x on top, we must push z, then y, then x.

Test your understanding!

Consider a CFG for balanced parentheses with the rule S -> (S).
According to the algorithm, what PDA transition corresponds to this production rule? Assume the PDA reads no input and pops S from the stack. What does it push back onto the stack?

Show answer

The right-hand side of the rule is (S). The reverse of this string is )S(.

The PDA transition would be: δ(q_loop, ε, S) = {(q_loop, )S()}.

This means when the PDA sees S at the top of the stack, it pops S and pushes ), then S, then (. The ( will be at the top of the stack, ready to be matched with the next input symbol.

3. A Complete Walkthrough

Let's see the algorithm in action. The following video provides a detailed, step-by-step construction of a PDA from a fairly complex CFG.

Context Free Grammar to Pushdown Automaton Conversion (CFG to PDA)

This video from Easy Theory is an excellent, detailed walkthrough of the entire conversion process for a specific grammar. The presenter methodically builds the PDA diagram from the CFG rules.

Watch from 01:59 to 19:58. This covers the full construction. Observe how: The initial transitions set up the stack with a marker ($) and the start symbol (S). Transitions are created to match and pop terminals (like 'a' and 'b'). For each grammar rule, a set of transitions is created to pop the variable and push the right-hand side in reverse order. Separate sets of transitions are needed for rules involving different variables (like 'S' and 'P').

To solidify your understanding, let's trace the execution for the simple grammar G for the language aⁿbⁿ where n ≥ 0.

  • Rules:

    1. S -> aSb
    2. S -> ε

  • Input string: ab

Here's how the constructed PDA would process this string (the top of the stack is on the left):

Step State Input Remaining Stack Action
1 q₀ ab $ Initial State
2 q₁ ab S$ (ε, ε -> S) - Push Start Symbol
3 q₁ ab bSa$ (ε, S -> aSb) - Expand S using Rule 1 (push b, then S, then a)
4 q₁ b bS$ (a, a -> ε) - Match input 'a', pop 'a' from stack
5 q₁ b b$ (ε, S -> ε) - Expand S using Rule 2 (push nothing)
6 q₁ ε $ (b, b -> ε) - Match input 'b', pop 'b' from stack
7 q₂ ε ε (ε, $ -> ε) - Pop final marker, empty the stack

Since the input is consumed and the stack is empty, the string ab is accepted. The sequence of non-deterministic choices (Step 3 and Step 5) corresponds to the derivation S => aSb => ab.

The Georgia Tech document we saw earlier also has an excellent trace example in section 1.2 for the language {aᵐbⁿ | m ≥ n}. I recommend reviewing it to see another example of the PDA in action.

Conclusion

Today, we've demonstrated a powerful and general method for converting any Context-Free Grammar into a Pushdown Automaton that recognizes the same language.

Key Takeaways:

  • The conversion works by creating a PDA that simulates a leftmost derivation of a string.
  • The PDA's stack holds the sequence of terminals and variables that still need to be processed.
  • The core of the algorithm involves three types of transitions:
    1. Initializing the stack with the start symbol.
    2. Matching terminals at the top of the stack with input symbols.
    3. Expanding variables at the top of the stack by replacing them with the reverse of a rule's right-hand side.
  • This construction proves that the class of languages generated by CFGs is a subset of the languages recognized by PDAs.

Preview of the Next Lesson:
We've now shown that L(CFG) ⊆ L(PDA). To complete the proof of equivalence between these two models, we must show the other direction: that for any PDA, we can construct an equivalent CFG. In the next lesson, we will explore the conceptual basis and the formal construction for converting a PDA back into a CFG. This is a more intricate process, but it will finalize one of the most important theorems in this course.