Series: Penn State Logic Seminar

Date: Tuesday, February 18, 2003

Time: 2:30 - 3:45 PM

Place: 113 McAllister Building

Speaker: Christopher Griffin, Penn State, ARL

Title: An Introduction to Context Free Languages via Push Down Automata


In this seminar, we introduce and explore the class of context free
languages (CFL) from the point of view of push down automata.
Informally, a push down automaton is a finite state machine with a
read/write stack. Unlike register machines, push down automata (and
finite state machines) may have non-deterministic state
transitions. We shall focus on the closure properties of CFL and on
some of the differences between deterministic and non-deterministic
push down machines.  Applications to programming languages will be
emphasized. If time is sufficient, we will give a short proof showing
that we can construct a push down automaton to recognize formulas in
finite propositional calculus (i.e. languages with a finite number of
symbols and no quantifiers). No prior knowledge will be assumed in
this talk.