These are my notes from a course that I taught at Villanova in the Fall of 1996, CSC 4710. The textbook was An Introduction to Formal Languages and Automata by Peter Linz, ISBN 0-669-17342-8. I used this material again in 1999 in CSC 8510.
The course material has not changed in any significant respects, and the textbook is quite similar to Introduction to the Theory of Computation by Michael Sipser.
What has changed, however, is HTML. You may find some amusement in noticing that all the images, including the non-ASCII characters, are .gif bitmaps. This is a Unicode-free set of notes! Also, I had a lot of links to external sites, almost all of which are now broken; I've removed them. Now that we have Google and Wikipedia, I don't see any need to find comparable links.
| Lecture | Topic |
| 1 | Introduction and review |
| 2 | BNF |
| 3 | Fundamental concepts (most important!) |
| 4 | DFAs and their implementation |
| 5 | NDFAs and their implementation |
| 6 | DFAs = NDFAs |
| 7 | Regular expressions |
| 8 | Regular expressions denote regular languages |
| 9 | Regular grammars |
| 10 | Closure, homomorphism |
| 11 | Pigeonhole principle, pumping lemma (difficult) |
| - | Review for midterm |
| - | Midterm exam |
| 12 | CFGs |
| 13 | Parsing and ambiguity |
| 14 | Pushdown automata |
| 15 | NPDAs & CFGs |
| 16 | A pumping lemma for cfgs (still difficult) |
| 17 | Turing machines |
| 18 | Universal Turing Machines and LBAs |
| 19 | Recursively enumerable languages |
| 20 | Unrestricted grammars |
| 21 | The Chomsky hierarchy |
| 22 | Undecidable problems |
| 23 | Church's Thesis |
| 24 | Complexity Theory, P and NP |
| 25 | Review for Final |
| - | Go over homework, Q & A |
| - | Final exam 5:30-7:30 |
Copyright © 1996 by David Matuszek
Last modified Feb 17, 2012