Course Material

Pushdown Automata book chapter
Hendrik Jan Hoogeboom and Joost Engelfriet, Pushdown Automata. Chapter 6 in: Formal Languages and Applications (C. Martín-Vide, V. Mitrana, G. Paun, eds.), Studies in Fuzziness and Soft Computing, v. 148, Springer, Berlin, pp. 117-138, 2004.

Slides (complete set 1.7Mb; small images, with notes)
I. The model (Introduction & motivation)
II. PDA and context-free languages
III. Determinism
V. Closure and Determinism (Stack languages and Predicting machines)
VI. Pushdown as storage (Abstract Families of Automata)
VIII. Famous Automata (Examples / Exercises)

Exercises and solutions.
In progress.

Pushdown Automata

This web site records some material for a course in the International PhD School in Formal Languages and Applications (Rovira i Virgili University, Tarragona, Spain). Slides were hand written, but a large part has been converted into electronic format. (They have not yet been put to classroom test, you are the first to spot the typo's.)

More General Introduction

Introduction to Pushdown Automata, based on our book chapter, but with explanations, and extra examples added from the transparencies of the course in Tarragona. Work in progress.

Other Sources

J.-M. Autebert, J. Berstel, L. Boasson. Context-Free Languages and Push-down Automata. In: Handbook of Formal Languages, Vol. 1 (G. Rozenberg, A. Salomaa, eds.) Springer, Berlin, 1997.
via citeseer


up up2