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. Version 2.3, Summer 2010, was a minor update from Version 2.2, which was published in Fall 2006. Version 2.3.1 is an even smaller update of Version 2.3. Version 2.3.2 is identical to Version 2.3.1 except for a change in the license under which the book is released. This book can be redistributed in unmodified form, or in modified form with proper attribution and under the same license as the original, for non-commercial uses only, as specified by the Creative Commons Attribution-Noncommercial-ShareAlike 4.0 License. (See http://creativecommons.org/licenses/by-nc-sa/4.0/) This textbook is available for on-line use and for free download in PDF form at http://math.hws.edu/FoundationsOfComputation/ and it can be purchased in print form for the cost of reproduction plus shipping at http://www.lulu.com