SPECIAL OFFERS
Keep up with new releases and promotions. Sign up to hear from us.
Register your product to gain access to bonus material or receive a coupon.
Enables students to focus on propositional and predicate logic and formal models of language—both with applications.
Engages students in abstract conceptual material that will actually help them as computer scientists.
Helps students understand the usefulness of theory.
Introduces students to important programming languages based on the two major topics of this book—thereby emphasizing their value.
Helps students understand the usefulness and applicability of theory and mathematical reasoning to their chosen field of study.
Aids student comprehension of abstract theories.
Instills appreciation of rigorous argumentation and helps students achieve it.
Alerts students to key concepts and motivates them to achieve their learning goals.
This book invites the reader to explore abstractions that are crucial to computer science. The authors bring a sense of excitement to logics, formal languages and automatamotivating topics by linking them to computing and to computational applications, sometime with whole chapters. They achieve exceptional clarity through a plethora of examples and figures, yet without-losing sight of, and indeed celebrating, the precision that is the hallmark of this subject matter.
Features of the book include:
1. Mathematical Preliminaries.
Operators and Their Algebraic Properties. Sets. Strings. Relations and Functions. Growth Rates of Functions. Graphs and Trees. Computing with Mathematical Objects.
I. LOGIC FOR COMPUTER SCIENCE.
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.
II. LANGUAGE MODELS FOR COMPUTER SCIENCE.
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.So you are a computer science (CS) major and you are sitting down to see what this book is about. It has been assigned, the course is required, you have no choice. Still you chose your institution, your major. Maybe your instructor made a good choice. Let's hope so.
Okay, you are not a computer science major, perhaps not even a student, but you have picked up this book. Maybe the title intrigued you. Will you be able to read it, to learn from it? We think so. We will try to interest you too.
Or you are teaching a course that might use this book, maybe in discrete math, maybe including logics or formal language or both. If you want your CS students to see the applicability of mathematical reasoning to their own field or your math students to see the usefulness of their field outside itself, it is your students whom we have in mind.
If you are a CS major, you have already noticed that this course is different from the others you have taken so far. It is not an introduction to computing, programming, problem solving, or data structures. No, this book is about something called modelsmodels of language and knowledge. It is also about formal methods.
You know something about models if you have built or seen a model airplane. In Kitty Hawk, North Carolina, you can see the wind tunnel that the Wright brothers built to test the lift capabilities of various wing shapes. A model can help us simplify and think more clearly about a complex problem (powered flight) by selecting a part (the wing) and focusing on some aspect of it (its aerodynamics). The other, temporarily ignored parts and aspects must ultimately be addressed, of course, if the original problem is to be solved.
The models in this book are simplifications too, but not of material objects like airplanes. For computer scientists, the objects of study lie mainly in the world of symbols. In this book, it is computer software, and especially the programming languages in which that software is written, from which we draw our models and to which we apply them.
A model, then, is a collection of precisely stated interacting ideas that focus on a particular aspect or part of our subject matter. A good model can simplify a topic to its essence, stripping away the details so that we can understand the topic better and reason precisely about it. The model keeps only those parts and processes that are of interest.
We reason both formally and informally. Informal methods draw on analogies to your knowledge of other things in the world in general and your common sense, typically expressed in a human language like English and perhaps a diagram. Formal methods use abstract symbolslike the famous "x" of high school algebraand clearly stated rules about how to manipulate them. A formal method based on a simple but precise model of a situation can enable us to prove that we have got things right at least as reflected in the model.
If this concern with precision and proof makes you think this is a theory book, you are partly right. If you think that means it is not of practical value, we ask you to think again. It is often said that experience is the best teacher. However, learning from experience means transferring ideas across situations by seeing the essential similarities in nonidentical situations. This abstracted essence, by which we learn from history or from our mistakes, is an informal model. Formalizing the model and reasoning carefully about itthat is, theoryis the scientist's and engineer's path to knowledge and action in the real world.
So what do we theorize about? We have chosen to focus on language, the crucial link between hardware and software. Programming languages permit software to be written and language processorscompilers, interpreters and assemblerspermit hardware to run that software. Sometimes a model proves to be so interesting and widely applicable that it becomes an object of study in its own right. That is the case with the logic and language models in this book.
Two key aspects of language are structure and meaning. We study models of each. The structure of language has to do with the arrangement of symbols into permitted sequencescalled sentences in human language and statements in programming languages. This topic is usually called formal models of language. It underlies key aspects of compilers, the study of what computers can do efficiently and the processing of human language for translation and easy interaction between people and computers.
Symbol arrangements are of interest not only in their own right, but also because they express ideas about meaning and computation. Expressing meaning can be done in various ways, including logic. Of the many logics, the simplest is propositional logic. It finds application-in the tiny hardware components called logic gates, in the conditions for branching and loops in high-level programming languages and in mathematical rules of proof that can be applied via software throughout engineering and science. Predicate logic builds on propositional logic to permit knowledge representation in database systems, artificial intelligence, and work on program correctness in software engineering.
Computer science students may notice that several phrases in the prior paragraphs are the names of upper division courses in computer science. To further emphasize the practical value of the two major topics of this book, we introduce an important programming language based on each. Lex, based on formal language, is a tool for building a lexical scannera key component of a compiler. Prolog, a programming language whose core is based on predicate logic, supports rapid prototyping of intelligent systems.
Formalisms for language and logic have ancient roots: India for language and Greece for logic. Each field has enjoyed renewed attention in more recent times, starting in the nineteenth century for logic and early in the twentieth century for language. These latter thrusts are more formal yet still independent of computing. The venerable histories of logic and linguistics suggest the inherent fascination that each has held for human minds. Building on that motivation, this book stresses the relationship of each to computer science. The two fields are also related to each other in various ways that emerge in this text. Watch for these important links among logic, formal language, and computing.
H. HAMBURGER
D. RICHARDS