Foundations of Computation
Carol Critchlow, Hobart and William Smith Colleges
David Eck, Hobart and William Smith Colleges
Pub Date: 2011
Conditions of Use
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, 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.
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 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
- Chapter 1: Logic and Proof
- Chapter 2: Sets, Functions, and Relations
- Chapter 3: Regular Expressions and FSA's
- Chapter 4: Grammars
- Chapter 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.