Foundations of Computation

by Carol Critchlow & David J. Eck

Read here Read at LibreTextsPDF

Foundations of Computation is a free textbook for a one-semester course in theoretical computer science. 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.

Description from LibreTexts.

Publisher
Hobart and William Smith Colleges
Subjects
Engineering, Computer Science
Licence
CC BY-NC-SA, as LibreTexts states it. Non-commercial use only.
Who can read
Tweens profiles and older, judged from its title and subjects

Contents

LibreTexts writes equations in TeX, and here they show as TeX; the PDF has them typeset.

  1. Front Matter
  2. TitlePage
  3. InfoPage
  4. Table of Contents
  5. Licensing
  6. 1: Logic and Proof
  7. 1.1: Propositional Logic
  8. 1.2: Boolen Algebra
  9. 1.3: Application - Logic Circuits
  10. 1.4: Predicates and Quantifiers
  11. 1.5: Deduction
  12. 1.6: Proof
  13. 1.7: Proof by Contradiction
  14. 1.8: Mathematical Induction
  15. 1.9: Application- Recursion and Induction
  16. 1.10: Recursive Definitions
  17. 2: Sets, Functions, and Relations
  18. 2.1: Basic Concepts
  19. 2.2: The Boolean Algebra of Sets
  20. 2.3: Application- Programming with Sets
  21. 2.4: Functions
  22. 2.5: Application- Programming with Functions
  23. 2.6: Counting Past Infinity
  24. 2.7: Relations
  25. 2.8: Relational Databases
  26. 3: Regular Expressions and FSA's
  27. 3.1: Languages
  28. 3.2: Regular Expressions
  29. 3.3: Using Regular Expressions
  30. 3.4: Finite-State Automata
  31. 3.5: Nondeterministic Finite-State Automata
  32. 3.6: Finite-State Automata and Regular Lan- guages
  33. 3.7: Non-regular Languages
  34. 4: Grammars
  35. 4.1: Context-free Grammars
  36. 4.2: Application - BNF
  37. 4.3: Parsing and Parse Trees
  38. 4.4: Pushdown Automata
  39. 4.5: Non-context-free Languages
  40. 4.6: General Grammars
  41. 5: Turing Machines and Computability
  42. 5.1: Turing Machines
  43. 5.2: Computability
  44. 5.3: The Limits of Computation
  45. Back Matter
  46. Index
  47. Index
  48. Glossary
  49. Detailed Licensing