Foundations of Computation

Foundations of Computation by Carol Critchlow and David Eck provides a thorough introduction to the theoretical foundations underlying computation and programming languages.

Recommended For: The textbook is suitable for a one-semester course in theoretical computer science and can be used as either a standalone text or supplementary material. It has no prerequisites other than introductory computer programming, making it accessible to a wide range of students.

You Will:

Learn essential discrete mathematics topics like logic, sets, functions, and relations
Understand formal languages and automata theory, including formal grammar, regular expressions, and finite state automata
Explore computability theory and Turing machines to understand what problems are solvable by a computer
Engage with numerous examples, exercises, and select Python code samples to reinforce your understanding

Detailed Overview

Foundations of Computation is a comprehensive open textbook that systematically builds students’ understanding of the theoretical foundations of computation and programming languages. Spanning five chapters, the book begins by covering essential discrete mathematics concepts, including logic, sets, functions, and relations.

The text then delves into formal languages and automata theory, teaching students about formal grammar, regular expressions, finite state automata, and more. Subsequent chapters introduce computability theory and Turing machines, examining the limits of what problems can be solved by a computer.

Throughout the textbook, the authors employ clear writing, a modular structure, and a wealth of examples, exercises, and select Python code samples to guide students through the course material. This approach helps to make the often-abstract concepts of theoretical computer science more accessible and engaging for learners.