Course Material
Pushdown Automata book chapterHendrik 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
...
