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

Abstract: 

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.