External
Foundations of Computation
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.
- Author
- Carol Critchlow & David J. Eck
- Publisher
- Hobart and William Smith Colleges
- Source
- LibreTexts
- License
- CC BY-NC-SA
- Language
- EN
- Category
- Information Technology
Contents· 39 sections
- 01: Logic and Proof
- 1.01: Propositional Logic
- 1.02: Boolen Algebra
- 1.03: Application - Logic Circuits
- 1.04: Predicates and Quantifiers
- 1.05: Deduction
- 1.06: Proof
- 1.07: Proof by Contradiction
- 1.08: Mathematical Induction
- 1.09: Application- Recursion and Induction
- 1.10: Recursive Definitions
- 02: Sets Functions and Relations
- 2.01: Basic Concepts
- 2.02: The Boolean Algebra of Sets
- 2.03: Application- Programming with Sets
- 2.04: Functions
- 2.05: Application- Programming with Functions
- 2.06: Counting Past Infinity
- 2.07: Relations
- 2.08: Relational Databases
- 03: Regular Expressions and FSA's
- 3.01: Languages
- 3.02: Regular Expressions
- 3.03: Using Regular Expressions
- 3.04: Finite-State Automata
- 3.05: Nondeterministic Finite-State Automata
- 3.06: Finite-State Automata and Regular Lan- guages
- 3.07: Non-regular Languages
- 04: Grammars
- 4.01: Context-free Grammars
- 4.02: Application - BNF
- 4.03: Parsing and Parse Trees
- 4.04: Pushdown Automata
- 4.05: Non-context-free Languages
- 4.06: General Grammars
- 05: Turing Machines and Computability
- 5.01: Turing Machines
- 5.02: Computability
- 5.03: The Limits of Computation