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.