Introduction to the general theory of computation. Formal grammars: regular, context-free, and context-sensitive languages. Formal automata: finite-state and pushdown models. Decidability. Turing Machines. The Chomsky hierarchy. NP-Completeness and Complexity Theory.
