Logic and Language Models for Computer Science

Operators and Their Algebraic Properties. Sets. Strings. Relations and Functions. Growth Rates of Functions. Graphs and Trees. Computing with Mathematical Objects.

2. Propositional Logic.

Propositions. States, Operators, and Truth Tables. Proofs of Equivalence with Truth Tables. Laws of Propositional Logic. Two Important Operators.

3. Proving Things: Why and How.

Reasons for Wanting to Prove Things. Rules of Inference. Proof by Rules. Assumptions. Proof Examples. Types of Theorems and Proof Strategies.

4. Predicate Logic.

Predicates and Functions. Predicates, English, and Sets. Quantifiers. Multiple Quantifiers. Logic for Data Structures.

5. Proving with Predicates.

Inference Rules with Predicates. Proof Strategies with Predicates. Applying logic to Mathematics. Mathematical Induction. Limits of Logic.

6. Program Verification.

The Idea of Verification. Definitions. Inference Rules. Loop Invariants. The Debate About formal Verification.

7. Logic Programming.

The Essence of Prolog and Its Relation to Logic. Getting Started Using Prolog. Database Operations in Prolog. The General Form and a Limitation of Prolog. How Prolog Works. Structures. Lists and Recursion. Built-in Predicates and Operators.

8. Language Models.

Programming Languages and Computer Science. Ambiguity and language Design. Formal Languages. Operations on Languages. Two levels and Two Language Classes. The Questions of Formal Language Theory.

9. Finite Automata and Their Languages.

Automata: The General Idea. Diagrams and Recognition. Formal Notation for Finite Automata. Finite Automata in Prolog. Nondeterminism: The General Idea. Nondeterministic Finite Automata. Removing Nondeterminism. A-Transistions. Pattern Matching. Regular Languages.

10. Regular Expressions.

Regular Sets. Regular Expressions and What They Represent. All Regular sets Are FA Languages. All FA languages Are Represented by Res.

11. Lex: A Tool for Building Lexical Scanners.

Overview. Lex Operators and What They Do. The Structure and processing of Lex Programs. Lex Examples with C. States. Using Lex in Unix. Flex and C++.

12. Context-Free Grammars.

Limitations of Regular Languages. Introduction to Context-Free Grammars. RE Operators in CFGs. Structure, Meaning, and Ambiguity. Backus Normal form and Syntax Diagrams. Theory Matters.

13. Pushdown Automata and Parsing.

Visualizing PDAs. Standard Notation for PDAs. NPDAs for CFG Parsing Strategies. Deterministic Pushdown Automata and Parsing. Bottom-Up Parsing. Pushdown Automata in Prolog. Notes on Memory.

14. Turing Machines.

Beyond Context-Free Languages. A Limitation on Deterministic Pushdown Automata. Unrestricted Grammars. The Turing Machine Model. Infinite Sets. Universal Turing Machines. Limits on Turing Machines. Undecidability. Church-Turing Thesis. Computational Complexity.

Index.