# Foundations of Computation

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

## Formats Available

## Conditions of Use

Attribution-NonCommercial-ShareAlike

CC BY-NC-SA

## Reviews

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

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 would also be welcome.

No errors detected

Content is update, but there haven't been any recent developments for this topic.

Writing is clear and concise. The informal restatements are helpful for the students to grasp the topic.

Notation is standard and consistent.

The first part could serve as a brief review on discrete math.

Although the mathematical background is useful, more space could be dedicated to FSAs, DFAs, and TMs.

Links within the pdf would be helpful. I read in another review that the Latex source was available. This is a big plus.

No grammatical issues.

Reference to Santa, but that is fine.

Overall, a good text. Could use a bit more in the second half (DFA/FSA/TM) and computability. I would also like to see reducibility and undecidable languages discussed.

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

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 text:

* Section 1.3 on Logic Circuits does not cover NAND/NOR gates, Karnaugh maps, gate delays, or common circuits such as adders and multiplexers. It only hints at sequential logic, and does not return to the topic in Chapter 3 when talking about finite-state automata.

* Section 1.5 talks about Deduction, but does not include a complete set of rules (it says "There are many other rules. Here are a few that might prove useful."); it would have been easy here to include a full set of natural deduction (introduction and elimination) rules, at least for propositional logic.

* Section 1.8 on Induction is only about induction on the natural numbers, and even when the examples of recursion in Section 1.9 (in Java) include binary trees the induction is performed "on the number of nodes", rather than introducing the (much clearer, in my opinion) notion of structural induction. I also take the opportunity to use a language such as Scala or Haskell in which recursion is more natural (and I continue to use this language in Section 2.5 when talking about programming with first-class functions). Similarly, the recursive definitions in Section 1.10 are only over the natural numbers.

* Section 3.3 on Regular Expressions briefly mentions character classes, but does not address how to deal in a practical way with Unicode character classes (which should not just be treated as the "or" of all characters in the class).

* Section 4.3 works with parse trees, but it does not go on to talk about abstract syntax trees, which I find to be a good connection between parsing and recursive functions (such as a simple interpreter) on trees.

I have not found any errors (except I prefer to use the term "combinational logic" instead of "combinatorial logic", which I believe is a common mistake).

Apart from the comments above about the somewhat dated use of Java (and later C++) for programming examples where a more modern functional language (or even the recent functional additions to Java and C++) would be more appropriate, there is very little in this text that will go out of date any time soon.

I started using this text precisely because Critchlow and Eck provide clearer coverage of these topics than any of the other (free) books I have tried, and certainly clearer than what I have been able to produce on my own.

The only complaint I have about consistency relates to the point made earlier about not introducing structural induction, and yet in Chapter 3 there is at least one proof (about converting regular expressions to finite-state automata) that uses structural induction!

So far, I have found it reasonably easy to merge sections of this text with my own supplemental materials. I was able to take several sections out of Chapters 1 and 2, rearrange them, and add in material (particularly on logic circuits and functional programming) to meet my needs fairly well.

The organization is fairly standard for these topics.

The PDF available to download does not have internal links (from the table of contents or the index). However, the LaTeX source files are available and it is easy to generate a new version in which these links are present.

I have not seen any issues with the grammar.

There is very little in this book to which this even applies -- most examples are about mathematical rather than cultural objects.

I am enjoying using the Critchlow and Eck book with my classes. Although it does not cover as much as the (now 25-year-old) Aho & Ullman text that I used to use, I am pleased with its accessibility, as well as the ease with which I have been able to rearrange and supplement it.

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

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 model for those considering curriculum redesign.

In addition, selected content may serve well to supplement other, more comprehensive, textbooks.

No errors detected.

The content area addressed is one of the more stable within computer science. Examples given in a specific programming language (Java) and references to particular language definitions (C++) appear to be relatively easy to modify/replace in future versions. The section of applications to databases using SQL may need greater reworking.

The text is well-written but may pose some difficulty for the intended audience: "It has no prerequisites other than a general familiarity with computer programming." There are some oddities in language usage, for example referring to a wire "as being on and off", that can be useful simplifications or can cause unnecessary confusion depending on the specific background of the reader.

Tone is largely consistent.

Chapters and Sections are . The material is (necessarily) self-referential such that reordering of the sections would not be viable.

The content may serve well as a supplement other textbooks.

The internal organization is consistent with the perceived intended presentation.

Text and images appear crisp and clear.

There are no internal links within the PDF (such as for the Table of Contents or Index) so navigation is linear.

Accessibility issues (such as those articulated at Section508.gov) do not appear to have been taken into account.

No errors identified.

The text has little cultural relevance (minor historical references) and no intentionally insensitive, biased, or offensive content observed.

Instructors may find value in extracting and using parts of this work to supplement other materials and textbooks.

The PDF has some issues with accessibility. For example, a text-to-speech reader skipped multiple phrases within sentences, did not handle footnote text properly, and did not address tables, mathematical notation, or diagrams.

Readers would benefit from a greater number of worked-through examples.

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

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 logic are covered in other classes. As far as the coverage of languages, grammars and automata, the book hits highlights in each topic. I would like to see more in-depth discussions on topics, such as different grammatical formats, Chomosky hierarchy, decidability, variations on the turing machine, etc.

The content appear to be technically accurate.

This is a good introduction of computer theory, aka computational theory, grammars, formal languages, etc. While this subject is well-understood since the 60's, it is definitely still relevant to computing and software development today. This is usually the course before compilers. As long as we are still programming with textual language, this topic is still very relevant.

The writing is pretty clear. I think maybe the formatting is making it a little harder to read. The book feels very compact and concise with a lot of materials packed in.

Consistency is good.

The chapter and section divisions are good.

The organization and structure flow is good too. I would like to see more examples but overall it is good.

No interface issues. I would like to see more graphics/illustrations though.

No issues.

Not applicable in this case.

This is a good introductory book. I would need to supplement it with additional materials however for a semester or quarter long course. I don't normally cover logic and discrete math in such detail (over half of the book). We have separate classes for Discrete Math and Logic.

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

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; re-explaining neatly the basic technical words that will be coming in latter chapters.

It has some Python programming code in it, so that is a plus. But it has fewer diagrams and problems about PDAs, NFAs, and DFAs than the current book that we are using (Sipser).

I did not find any inaccuracies.

The text is by-and-large up-to-date. But then again, this topic is mature having been formulated and formalized in the 1930s through the 1960s.

The writing is easy and clear. The author uses second person perspective to explain things which makes the book interactive.

It is quite good.

The book is, in fact, easy to subdivide into smaller modules. It will be easy to re-organize the course content if and when time becomes an issue (common around here because of the threat of hurricanes during the storm season).

Topics are presented in a suitable manner. However, FSAs are introduced a tad too late for my taste. And, as mentioned before, there are only a limited number of PDA, FSA, NFA problems.

No noticeable interface issues were encountered.

No grammatical errors were found.

As a textbook about the Theory of Computation, this criterion is marginally relevant. That being said, there were no obvious references to race, ethnicity, or background.

I am happy that this book is available on an "open" basis. At the very least, this book could serve as a good reference and balancing tool for students enrolled in my CSCI 3102 classes. I am willing to even adopt it as a primary textbook after this Spring 2017 semester where I have already made arrangements to use Sipser for the course.

## 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

## Ancillary Material

## 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

### Authors

**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.