CSci 301 Lecture Notes
Week Three, Thursday: Pushdown Automata
We have seen the equivalence of regular languages and DFAs. Now we establish
the equivalence of CFGs and PDAs.
Formal Definition of a PDA
Definition 2.8.
Examples of PDAs
Examples 2.9, 2.10, and 2.11.
Equivalence with CFGs
Theorem 2.12.
Lemma 2.13.
Example 2.14.
Lemma 2.15
Homework Assignment
Assigned Thursday, September 24, due Thursday, October 1, at beginning of class.
Chapter 2:
Exercises 2.1, 2.4.
Email: Richard dot J dot Wagner at gmail dot com
notes03b.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by
Rick Wagner. Copyright © 1998-2011, all rights reserved.