1 Introduction
2 BNF
3 Languages and grammars (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)
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 Final Review

© 1996 David Matuszek