CS 360: Resources

Winter 2016, Introduction to the Theory of Computation

Textbook

The following book is the textbook for the course; be sure to check the book's home page for errata: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, third edition, Addison-Wesley, 2007.

Supplementary materials

The following additional notes supplement the text; please see the schedule to see for what lectures each is most relevant.

• Introductory material (PDF)
• Regular expression identities (PDF)
• Kleene's Theorem (PDF)
• Closure property proof recipes (PDF)
• Decision problems for regular languages (PDF)
• Equivalence of languages (PDF)
• Pumping lemma notes (PDF)
• Context-free languages (PDF)
• Turing machines (PDF)

Slides used in class

In the event that I choose to project material during a lecture, the material (with the exception of self-tests) will be linked in here.