Watch a video introduction to this course on YouTube.
To give a basic introduction to the theoretical foundations of computer science.
Some exposure to the theoretical foundations of Computer Science is considered useful for all CS graduates, especially for anyone intending to continue studies at the graduate level.
Prerequisites: (CS 240 or SE 240), CS 241, (MATH 239/249 or CO 103), (CS 245 or SE 112/212); Computer Science students only.
Antirequisites: CS 365.
Successors: CS 462.
Introduction to Automata Theory Languages & Computation 3rd ed., by Hopcroft, Motwani & Ullman, Published by: Addison Wesley (required)
3 hours of lectures per week. Normally available in Fall, Winter and Spring
Deterministic and non-deterministic finite automata and their equivalence. Equivalence with regular expressions. Closure properties. The pumping lemma and applications.
Definitions. Parse trees. The pumping lemma for CFLs and applications. Normal forms. General parsing. Sketch of equivalence with pushdown automata.
Designing simple TMs. Variations in the basic model (multi-tape, multi-head, non-determinism). Church-Turing thesis and evidence to support it through the study of other models.
The undecidability of the halting problem. Reductions to other problems. Reduction in general.
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-uops@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Tuesday, 14-Feb-2012 11:28:36 EST
