ITEC 420 - Section 2.2 - Pushdown Automata

Pushdown Automata (PDA) - The Big Picture

PDA: Operations and Computation

PDA: First Examples

PDA: First Example Revisited

Testing for Empty Stack and End of Input

PDA: Stack and Machine Operations

PDA: Formal Definition

PDA: More Examples

Theorem 2.20 = CFL = PDA

Lemma 2.21: CFG → PDA - Example

Lemma 2.21: CFG → PDA - Basic Idea

Lemma 2.21: CFG → PDA - Application to Compilers

Lemma 2.21: CFG → PDA - Informal Algorithm

  1. Place marker $ and the start variable on the stack

  2. Repeat forever:
    1. If the top of stack is variable symbol A, then:

    2. If the top of the stack is terminal a, read the next input symbol from the input and compare it to a.

    3. If the top of the stack is $, enter the accept state. Doing so accepts the input, if it has all been read.

  3. The substitutions in the branch of the nondeterminism that succeeds will follow the substitutions of a leftmost derivation.

  4. The stack contents will be the strings of a derivation, minus the initial symbols that are matched.

Lemma 2.21: CFG → PDA - Shorthand Notation

Lemma 2.21: CFG → PDA - Formal Definition

CFG → PDA: Another Example

CFG → PDA: Showing it Works

Now the other way: PDA → CFG

PDA → CFG: Main Idea

A Standard Form for PDA P

Apq and the Strings it Generates

PDA → CFG: Building the Grammar

Grammar Rules and Computations

PDA → CFG: Examples 1 and 2

PDA → CFG: Example 3


Regular Languages are Context Free Languages