Announcements:
Course outline [pdf]
Policies on grading and course work
[html]
There is no required text for the course.
Students interested in an additional source beyond the course
notes may find the following text to be helpful:
M. Sipser.
Introduction to the Theory of Computation
(Third Edition).
Cengage Learning, 2012.

(An older edition of this book would serve just as well for this
course.)
Notes for each lecture are linked below.
You can also download all 21 lectures in a single pdf file
[pdf].
Before you send this file to a printer, please observe that
it is about 230 pages long, and consider using an electronic copy
instead.
May 6 
Lecture 1. Course overview and mathematical foundations
[pdf]

May 8 
Lecture 2. Countability for languages and deterministic finite
automata
[pdf]

May 13 
Lecture 3. Nondeterministic finite automata
[pdf]

May 15 
Lecture 4. Regular operations and regular expressions
[pdf]

May 20 
Victoria Day – no lecture

May 22 
Lecture 5. Proving languages to be nonregular
[pdf]

May 27 
Lecture 6. Further discussion of regular languages
[pdf]

May 29 
Lecture 7. Contextfree grammars and languages
[pdf]

June 3 
Lecture 8. Parse trees, ambiguity, and Chomsky normal form
[pdf]

June 5 
Lecture 9. Closure properties for contextfree languages
[pdf]

June 10 
Exam 1 (in class)

June 12 
Lecture 10. Proving languages to be noncontextfree
[pdf]

June 17 
Lecture 11. Pushdown automata
[pdf]

June 19 
Lecture 12. Stack machines
[pdf]

June 24 
Lecture 13. Decidable and semidecidable languages;
computable functions
[pdf]

June 26 
Lecture 14. Turing machines and their equivalence to stack
machines
[pdf]

July 1 
Canada Day – no lecture

July 2 
Lecture 15. Encodings; examples of decidable languages
[pdf]

July 3 
Lecture 16. Universal stack machines and a nonsemidecidable
language
[pdf]

July 8 
Lecture 17. Undecidable languages
[pdf]

July 10 
Lecture 18. Further discussion of computability
[pdf]

July 15 
Exam 2 (in class)

July 17 
Lecture 19. Timebounded computations
[pdf]

July 22 
Lecture 20. NP, polynomialtime mapping reductions, and
NPcompleteness
[pdf]

July 24 
Lecture 21. Ladner's theorem
[pdf]

July 29 
Lecture 22. Further discussion and summary
[no notes for this lecture]

August 2

Final exam
12:30–3 PM in STC 0010


Assignments will be posted as they become available.
If you like to typeset your solutions using LaTeX, feel free to
use the source files linked with each assignment.
Assignment 1 (due Thursday May 30)
[pdf,
LaTeX]

Assignment 2 (due Thursday June 20)
[pdf,
LaTeX]

Assignment 3 (due Thursday July 4)
[pdf,
LaTeX]

Assignment 4 (due Thursday July 25)
[pdf,
LaTeX]
