Abstract: This is an undergraduate course that provides an introduction to formal models of languages and computation. Topics covered include finite automata and regular languages, pushdown automata and context-free languages, Turing machines, computability, and NP-completeness.

The course is designed for CS majors and students who are interested in understanding computation.

Prerequisites: The course assumes the understanding of the program design, discrete structures, the foundations of symbolic logic, and mathematical maturity.