CSC 335 Notes 2 Chapter 6: Pushdown Automata (PDA)

PDA - the automata for CFLs

δ : The Transition Function

PDA for Lwwr

PDA as a state diagram

PDA for Lwwr: Transition Diagram

PDA’s Instantaneous Description (ID)

Principles about IDs

PDA for Lwwr: Proof of correctness

PF==> PN construction

Equivalence of PDAs and Equivalence of PDAs and CFGs

CFGs == PDAs ==> CFLs

Converting CFG to PDA

Converting a CFG into a PDA

Formal construction of PDA from CFG

Simulating g strin 0011 on the new PDA

Proof of correctness for CFG ==> PDA Proof of correctness for CFG ==> PDA construction

Converting a PDA into a CFG

Two ways to build a CFG

Deterministic PDAs

This PDA for Lwwr is non-deterministic
Deterministic PDA: Definition

PDA vs DPDA vs Regular languages