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.