This text presents the formal concepts underlying Computer Science.
It starts with a wide introduction to Logic with an emphasis on reasoning and proof, with chapters on Program Verification and Prolog.
The treatment of computability with Automata and Formal Languages stands out in several ways:
- it emphasizes the algorithmic nature of the proofs and the reliance on simulations;
- it stresses the centrality of nondeterminism in generative models and the relationship to deterministic recognition models
The style is appropriate for both undergraduate and graduate classes.
Readership: Students and professionals interested in theoretical computation and language models for computer science.
Table of Contents
Chapter 1 Mathematical Preliminaries
Part I logic For Computer Science
Chapter 2 Propositional Logic
Chapter 3 Proofs By Deduction
Chapter 4 Predicate Logic
Chapter 5 Proving With Predicates
Chapter 6 Program Verification
Part II language Models For Computer Science
Chapter 7 Language And Models
Chapter 8 Generative Models Of Regular Languages
Chapter 9 Finite Automata And Regular Languages
Chapter 10 Context-Free Grammars
Chapter 11 Pushdown Automata And Parsing
Chapter 12 Turing Machines
Appendix A logic Programming
Appendix B the Awk Language
Appendix C answers To Selected Problems