# Undergraduate Computer Science

# CS U390: Theory of Computation

Introduces the theory behind computers and computing aimed at answering the question: “What are the capabilities and limitations of computers?” Covers automata theory, computability, and complexity. The automata theory portion includes finite automata, regular expressions, non-determinism, non-regular languages, context-free languages, pushdown automata, and non-context-free languages. The computability portion includes Turing machines, the Church-Turing Thesis, decidable languages, and the Halting Theorem. The complexity portion includes big-O and small-o notation, the classes P and NP, the P versus NP question, and NP-completeness.

**Prerequisites:**

CSU213 and PHLU215 (Symbolic Logic).

**Credit hours:**4 SH