PrefaceAbout the Author1 Mathematical Preliminaries1.1 Sets and Sequences1.2 Relations and Functions1.3 Operators and Their Algebraic Properties1.4 Set Operators1.5 Strings and String Operators1.6 Expressions1.7 Growth Rates of Functions1.8 Graphs and TreesPart I Logic for Computer ScienceIntroduction to Part I Logic for Computer Science2 Propositional Logic2.1 Propositions2.2 Boolean Expressions2.3 States, Operators and Semantics2.4 Propositions as Functions2.5 Laws of Propositional Logic2.6 Two Important Operators2.7 Normal Forms2.8 Logic Circuits3 Proofs by Deduction3.1 Reasons for Wanting to Prove Things3.2 Natural Deduction Proofs3.3 A Very Formal Approach3.4 Rules of Inference3.5 Proof by Rules3.6 Assumptions3.7 A Larger Set of Rules3.8 Examples3.9 Types of Theorems and Proof Strategies3.10 Soundness and Completeness4 Predicate Logic4.1 Predicates and Functions4.2 Predicates, English, and Sets4.3 Quantifiers4.4 Quantification and Formal Definitions4.5 Examples from Data Structures5 Proofs with Predicates5.1 Inference Rules with Predicates5.2 Proof Strategies with Predicates5.3 Applying Logic to Mathematics5.4 Mathematical Induction5.5 Examples of Mathematical Induction5.6 Limits of Logic6 Program Verification6.1 The Idea of Verification6.2 Definitions6.3 Inference Rules6.4 Loop Invariants6.5 Examples of Search6.6 Proofs with Procedures6.7 Loop Invariants and Tail Recursion6.8 The Debate About Formal VerificationPart II Language Models for Computer ScienceIntroduction to Part II Language Models for Computer Science7 Language and Models7.1 Programming Languages and Computer Science7.2 Formal Languages7.3 Language Operators7.4 Two Views of Alphabets and Language7.5 Questions in Formal Language Theory7.6 Generative Models7.7 Non-determinism: The General Idea8 Generating Regular Languages8.1 Regular Languages8.2 Regular Expressions8.3 Grammars: The General Idea8.4 Regular Grammars8.5 A Bridging Model8.6 Deterministic Regular Grammars8.7 REs and Non-determinism8.8 Summary9 Finite Automata9.1 Finite Automata: The General Idea9.2 Diagrams and Recognition9.3 Formal Notation for Finite Automata9.4 Relationship to Regular Languages9.5 Non-deterministic Finite Automata9.6 Properties of Regular Languages9.7 Limitations of Regular Languages9.8 Pattern Matching9.9 Designing Finite Automata9.10 Digital Logic and Automata10 Context-Free Grammars10.1 Introduction to Context-Free Grammars10.2 An Example10.3 Structure, Meaning and Ambiguity10.4 Chomsky Normal Form10.5 Greibach Normal Form10.6 Beyond Context-Free Languages10.7 The Role of the Empty String11 Pushdown Automata and Parsing11.1 Motivating PDAs11.2 Standard Notation for PDAs11.3 From CFG to NPDA11.4 From NPDA to CFG11.5 Parsing11.6 DPDAs and Parsing11.7 A Variation of the PDA Model11.8 Limitations on DPDAs11.9 More on Parsing11.10 Notes on Memory12 Turing Machines12.1 Unrestricted Grammars12.2 The Turing Machine Model12.3 Infinite Sets12.4 Universal Turing Machines12.5 Limits on Turing Machines12.6 Undecidability12.7 Church-Turing Thesis12.8 Computational ComplexityAppendix A Logic ProgrammingA.1 Prolog and its Relation to LogicA.2 Getting Started Using PrologA.3 An Example Related to DatabasesA.4 The Form and Limitations of PrologA.5 How Prolog WorksA.6 StructuresA.7 Lists and RecursionA.8 Built-In Predicates and OperatorsA.9 Finite Automata in PrologA.10 Pushdown Automata in PrologAppendix B The AWK LanguageB.1 Overview of AWKB.2 Writing ExpressionsB.3 Writing Regular ExpressionsB.4 Writing PatternsB.5 Writing ActionsB.6 Using ArraysB.7 Sample ProgramsB.8 Using AWK in UnixB.9 An ExampleAnswers to Selected ProblemsBibliographyIndex