Computer ScienceFoundations of Computation
Not rated yetRate this bookFoundations of Computation by Carol Critchlow and David J. Eck connects mathematical reasoning with formal languages, machine models, and the limits of computation. This guide follows its five broad chapters, from logic and sets through automata, grammars, and Turing machines.
Free reading is available at the official source. Opens in a new tab.
FreeAbout this book
Foundations of Computation by Carol Critchlow and David J. Eck connects mathematical reasoning with formal languages, machine models, and the limits of computation. This guide follows its five broad chapters, from logic and sets through automata, grammars, and Turing machines.
How to study this book
Write precise definitions before attempting a construction or proof. For a language, distinguish the strings in the language from a recognizer or generator for it. Test small examples and counterexamples, but explain why the formal argument covers every case. Keep impossibility results separate from claims about practical running time.
Chapter-wise explanations and study tasks
Chapter 1 — Logic and Proof
Propositional and predicate logic, Boolean algebra, circuits, deduction, contradiction, induction, and recursion develop the reasoning tools used throughout the text. The form of a statement determines what counts as a proof. An example can suggest a theorem but cannot establish a universal claim.
Study task: Translate a quantified claim, negate it correctly, and prove a related simple statement using an explicitly justified method.
Chapter 2 — Sets, Functions, and Relations
Sets and their algebra organize collections; functions and relations describe mappings and structure. Programming applications and relational databases connect the abstractions with computation, while infinite-set arguments show where finite intuition fails. Check domains and definitions before relying on a familiar diagram.
Study task: Define a relation, test its properties, and compare a finite counting argument with a countability claim.
Chapter 3 — Regular Expressions and Automata
Formal languages, regular expressions, deterministic and nondeterministic finite automata describe a class of recognizable patterns. Constructions connect different representations, while nonregular-language arguments establish limits. Distinguish the book’s formal expressions from feature-rich programming-library syntax.
Study task: Construct an automaton and a formal regular expression for one small language, then justify a proposed nonregular example.
Chapter 4 — Grammars
Context-free grammars, BNF, parse trees, and pushdown automata extend the language framework. Ambiguity and non-context-free examples require reasoning about the formal system rather than only tracing one accepted string. General grammars broaden the hierarchy further.
Study task: Give a grammar for a small language, draw a parse tree, and test whether a selected string has competing parses.
Chapter 5 — Turing Machines and Computability
Turing machines provide a precise model for questions about what can be computed. Computability and limit arguments concern the existence of procedures under a model, not merely whether a current program is fast enough. State the problem’s input and required decision clearly.
Study task: Describe a simple machine computation and reconstruct the logical structure of one undecidability argument from the chapter.
Applied assignment
Create a formal-language portfolio containing a precise language definition, finite-automaton construction, equivalent regular representation where applicable, grammar and parse example, and a short computability argument. For each item, supply accepted and rejected test strings and explain why testing alone is not a proof of correctness.
Suggested reading plan
Work through Chapter 1 before proof-heavy later material. Use Chapter 2 to consolidate notation and mappings, Chapter 3 for finite-state models, Chapter 4 for grammar-based models, and Chapter 5 for general computation and limits. Revisit earlier examples when a more expressive model becomes available.
Questions for reflection
- Are you describing a language, generating it, or recognizing it?
- Which assumption limits the power of the model?
- Does the conclusion concern computability or efficiency?
Edition and source notes
This guide follows Critchlow and Eck’s five-chapter LibreTexts text. Its finite-state, grammar, and Turing-machine models are mathematical abstractions. The supplementary constructions and proof prompts are study tasks, not official solutions to the source exercises.
This page provides book information and study material. Full-text access is provided by the original publisher or authorised source; a listing does not grant permission to republish the book.
Read our Library Access & Copyright policyExplore the contents
Check the chapters covered in this edition.
Visit the official source
See reading, preview or purchase options.
Save for later
Keep this textbook in your saved collection.
Reader ratings & reviews
Share your thoughts
Your review helps other students choose the right resources.









