This unique compendium highlights the theory of computation, particularly logic and automata theory. Special emphasis is on computer science applications including loop invariants, program correctness, logic programming and algorithmic proof techniques. This innovative volume differs from standard textbooks, by building on concepts in a different order, using fewer theorems with simpler proofs. It has added many new examples, problems and answers. It can be used as an undergraduate text at most universities.
Author(s): Dana Richards, Henry Hamburger
Edition: 4
Publisher: World Scientific Publishing
Year: 2023
Language: English
Pages: 497
Contents
Preface
Preface to the Second Edition
Preface to the Third Edition
Preface to the Fourth Edition
About the Author
1 Mathematical Preliminaries
1.1. Sets and Sequences
1.2. Relations and Functions
1.3. Operators and Their Algebraic Properties
1.4. Set Operators
1.5. Strings and String Operators
1.6. Expressions
1.7. Growth Rates of Functions
1.8. Graphs and Trees
Exercises
Part I Logic for Computer Science
Introduction to Part I: Logic for Computer Science
2 Propositional Logic
2.1. Propositions
2.2. Boolean Expressions
2.3. States, Operators and Semantics
2.4. Propositions as Functions
2.5. Laws of Propositional Logic
2.6. Two Important Operators
2.7. Normal Forms
2.8. Logic Circuits
Exercises
3 Proofs by Deduction
3.1. Reasons for Wanting to Prove Things
3.2. Natural Deduction Proofs
3.3. A Very Formal Approach
3.4. Rules of Inference
3.5. Proof by Rules
3.6. Assumptions
3.7. A Larger Set of Rules
3.8. Examples
3.9. Types of Theorems and Proof Strategies
3.10. Soundness and Completeness
Exercises
4 Predicate Logic
4.1. Predicates and Functions
4.2. Predicates, English, and Sets
4.3. Quantifiers
4.4. Quantification and Formal Definitions
4.5. Examples from Data Structures
Exercises
5 Proofs with Predicates
5.1. Inference Rules with Predicates
5.2. Proof Strategies with Predicates
5.3. Applying Logic to Mathematics
5.4. Mathematical Induction
5.5. Examples of Mathematical Induction
5.6. Limits of Logic
Exercises
6 Program Verification
6.1. The Idea of Verification
6.2. Definitions
6.3. Inference Rules
6.4. Loop Invariants
6.5. Examples of Search
6.6. Proofs with Procedures
6.7. Loop Invariants and Tail Recursion
6.8. The Debate About Formal Verification
Part II Language Models for Computer Science
Introduction to Part II: Language Models for Computer Science
7 Language and Models
7.1. Programming Languages and Computer Science
7.2. Formal Languages
7.3. Language Operators
7.4. Two Views of Alphabets and Language
7.5. Questions in Formal Language Theory
7.6. Generative Models
7.7. Non-determinism: The General Idea
Exercises
8 Generating Regular Languages
8.1. Regular Languages
8.2. Regular Expressions
8.3. Grammars: The General Idea
8.4. Regular Grammars
8.5. A Bridging Model
8.6. Deterministic Regular Grammars
8.7. REs and Non-determinism
8.8. Summary
Exercises
9 Finite Automata
9.1. Finite Automata: The General Idea
9.2. Diagrams and Recognition
9.3. Formal Notation for Finite Automata
9.4. Relationship to Regular Languages
9.5. Non-deterministic Finite Automata
9.6. Properties of Regular Languages
9.7. Limitations of Regular Languages
9.8. Pattern Matching
9.9. Designing Finite Automata
9.10. Digital Logic and Automata
Exercises
10 Context-Free Grammars
10.1. Introduction to Context-Free Grammars
10.2. An Example
10.3. Structure, Meaning and Ambiguity
10.4. Chomsky Normal Form
10.5. Greibach Normal Form
10.6. Beyond Context-Free Languages
10.7. The Role of the Empty String
Exercises
11 Pushdown Automata and Parsing
11.1. Motivating PDAs
11.2. Standard Notation for PDAs
11.3. From CFG to NPDA
11.4. From NPDA to CFG
11.5. Parsing
11.6. DPDAs and Parsing
11.7. A Variation of the PDA Model
11.8. Limitations on DPDAs
11.9. More on Parsing
11.10. Notes on Memory
Exercises
12 Turing Machines
12.1. Unrestricted Grammars
12.2. The Turing Machine Model
12.3. Infinite Sets
12.4. Universal Turing Machines
12.5. Limits on Turing Machines
12.6. Undecidability
12.7. Church–Turing Thesis
12.8. Computational Complexity
Exercises
Appendix A: Logic Programming
A.1. Prolog and its Relation to Logic
A.2. Getting Started Using Prolog
A.3. An Example Related to Databases
A.4. The Form and Limitations of Prolog
A.5. How Prolog Works
A.6. Structures
A.7. Lists and Recursion
A.8. Built-In Predicates and Operators
A.9. Finite Automata in Prolog
A.10. Pushdown Automata in Prolog
Exercises
Appendix B: The AWK Language
B.1. Overview of AWK
B.2. Writing Expressions
B.3. Writing Regular Expressions
B.4. Writing Patterns
B.5. Writing Actions
B.6. Using Arrays
B.7. Sample Programs
B.8. Using AWK in Unix
B.9. An Example
Answers to Selected Problems
Chapter 1: Mathematical Preliminaries
Chapter 2: Propositional Logic
Chapter 3: Proofs by Deduction
Chapter 4: Predicate Logic
Chapter 5: Proofs with Predicates
Chapter 6: Program Verification
Chapter 7: Language and Models
Chapter 8: Generating Regular Languages
Chapter 9: Finite Automata
Chapter 10: Context-Free Grammars
Chapter 11: Pushdown Automata and Parsing
Chapter 12: Turing Machines
Appendix A: Logic Programming
Bibliography
Index
