Foundations of Computation

Foundations of Computation is a textbook for a one semester introductory course in theoretical computer science. It includes topics from discrete mathematics, automata theory, formal language theory, and the theory of computation, along with practical applications to computer science. It has no prerequisites other than a general familiarity with computer programming. More information is available at http://math.hws.edu/FoundationsOfComputation. Version 2.3, Summer 2010, offered minor updates and corrections from Version 2.2, plus a new section on pushdown automata. Version 2.3.1, Summer 2011, is an even smaller update, with one new proof and a few corrections. Version 2.3.2 is identical to 2.3.1 except for a change in license.