Theory of finite automata and regular expressions and properties of regular sets. Context-free grammars, context-free languages, and pushdown automata. Turing machines, undecidability problems, and the Chomsky hierarchy. Introduction to computational complexity theory and the study of NP-complete problems.