CIT 596 Theory of Computation

David Matuszek

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