These lecture notes may be used and distributed freely, for individual study or by course instructors. They may not be sold.

These notes were developed for the course CS 360 Introduction to the Theory of Computing at the University of Waterloo. Students registered in this course should be sure to check the course syllabus corresponding to the term for which they are registered—not all CS 360 instructors use these notes, and some that do may prefer older or alternative versions of them.

Latest update: October 19, 2020

All 20 lectures in one file (227 pages) [pdf]

1. Course overview and mathematical foundations [pdf]
2. Countability for languages; deterministic finite automata [pdf]
3. Nondeterministic finite automata [pdf]
4. Regular operations and regular expressions [pdf]
5. Proving languages to be nonregular [pdf]
6. Further discussion of regular languages [pdf]
7. Context-free grammars and languages [pdf]
8. Parse trees, ambiguity, and Chomsky normal form [pdf]
9. Properties of context-free languages [pdf]
10. Proving languages to be non-context free [pdf]
11. Pushdown automata [pdf]
12. Turing machines [pdf]
13. Variants of Turing machines [pdf]
14. Stack machines [pdf]
15. Encodings; examples of decidable languages [pdf]
16. Universal Turing machines and undecidable languages [pdf]
17. More undecidable languages; reductions [pdf]
18. Further discussion of computability [pdf]
19. Time-bounded computations [pdf]
20. NP, polynomial-time mapping reductions, and NP-completeness [pdf]

©2020 John Watrous