Read more about Foundations of Computation

Foundations of Computation

(5 reviews)

Carol Critchlow, Hobart and William Smith Colleges

David Eck, Hobart and William Smith Colleges

Copyright Year: 2011

Publisher: Carol Crichlow and David Eck

Language: English

Read this book

Conditions of Use

Attribution-NonCommercial-ShareAlike Attribution-NonCommercial-ShareAlike


Learn more about reviews.

Reviewed by Robert Marceau, Assistant Teaching Professor, University of Massachusetts Lowell on 6/9/20

A good amount of space dedicated to mathematical background. The book covers all topics with an appropriate depth for an undergrad. Additional exercises concerning FSAs, DFAs and PDAs would be welcome. A discussion of linear bounded automatons... read more

Reviewed by Brian Howard, Associate Professor of Computer Science, DePauw University on 10/15/19

The text is fairly comprehensive, although it is probably impossible to include all of the material on these topics that any given course (other than the authors', I assume) might need. Here are the areas where I have had to supplement the... read more

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.