Library Home

Foundations of Computation cover image

Foundations of Computation

(3 reviews)

Carol Critchlow, Hobart and William Smith Colleges

David Eck, Hobart and William Smith Colleges

Pub Date: 2011

Publisher: Independent

Language: English

Read this book

Conditions of Use



Learn more about reviews.

Reviewed by Jody Paul, Professor of Computer Science, Metropolitan State University of Denver on 4/12/19

The particular mix of curricular topics is somewhat unconventional. The content choices reduce the potential utility of this book for existing courses (e.g., discrete math, theory of computation). However, this particular design may serve as a... read more


Reviewed by Sherry Yang, Professor, Software Engineering Technology, Oregon Institute of Technology on 6/19/18

This is a good introductory book. In terms of coverage, I would like to see less logic and discrete math. A shorter review of logic, sets, functions and relations would be appropriate for a computational theory class. Normally discrete math and... read more


Reviewed by Nathanael DePano, Associate Professor, University of New Orleans on 2/15/17

The text covers all areas and ideas of the subject appropriately, missing only the last portion of the NP problem that is discussed in my class (CSCI 3102: Introduction to the Theory of Computation). Beginning chapters are very thorough;... read more


Table of Contents

  • 1 Logic and Proof
  • 2 Sets, Functions, and Relations
  • 3 Regular Expressions and FSA's
  • 4 Grammars
  • 5 Turing Machines and Computability

About the Book

Foundations of Computation is a free textbook for a one-semester course in theoretical computer science. It has been used for several years in a course at Hobart and William Smith Colleges. The course has no prerequisites other than introductory computer programming. The first half of the course covers material on logic, sets, and functions that would often be taught in a course in discrete mathematics. The second part covers material on automata, formal languages, and grammar that would ordinarily be encountered in an upper level course in theoretical computer science.

About the Contributors


Carol Critchlow, Associate Professor, Department of Mathematics and Computer Science, Hobart and William Smith Colleges. Critchlow received her PhD in Applied Mathematics from Cornell University in 1991 and joined the faculty of Hobart and William Smith Colleges the same year.

David J. Eck, PhD in Mathematics, Brandeis University, 1980. Professor, Department of Mathematics and Computer Science, Hobart and William Smith Colleges, Geneva, New York.