Regular expressions. Regular, context-free, and unrestricted grammars. Finite and pushdown automata. Turing machines and the halting problem; introduction to decidability.
Notes This course is crosslisted with CS 456. Credit at the 600-level requires additional work.