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, 241 and (MATH 239 or 249); 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.