Savitch W.J. Abstract Machines and Grammars

Little, Brown and Company, 1982. — 226 p.Computability theory is concerned primarily with determining what tasks can be accomplished by idealized computer programs. Formal language theory deals primarily with the ability of certain grammars to express the syntax of various types of languages. Both fields are branches of formal mathematics. The former theory has its roots in mathematical logic, the latter in mathematical linguistics which includes the mathematical theory of compiler design. In recent years, these two subjects have been studied extensively by computer scientists and have interacted to the point where, from the perspective of a computer scientist, they are frequently viewed as a single unified subject. As such, they have become a standard course topic in many computer science curricula. This book contains an introduction to these two interrelated subjects. It is suitable for an introductory course at either the advanced undergraduate or beginning graduate level. It also can be read and understood, without the aid of an instructor, by anybody who has either a background in theoretical mathematics or a reasonable amount of programming experience and some exposure to mathematical proofs.
The present text grew out of notes used in both graduate and undergraduate courses at the University of California at San Diego. These courses were designed for students with a good deal of experience in the areas of computer programming and systems, but with limited exposure to formal mathematics. This explains the slightly unorthodox arrangement of the material in this book. In teaching these courses it was found that the notion of a context-free grammar was easily understood by students who have had a fair amount of programming experience. In fact it proved to be the one notion in the course that they were most comfortable with. Primarily for this reason, the book presents context-free grammars first and uses these grammars as the central focus of the book. This approach, while it may not be the traditional way to structure the material, has proved to be pedagogically sound. It has also proved to be a sound and efficient approach mathematically, since context-free grammars turn out to be a convenient and efficient vehicle for presenting a number of other key notions in computability and formal language theory.
There are some points to keep in mind when using this book as a text. In reading this book you will find that a number of details are left as exercises. These exercises should be done by the student. They are usually not difficult, but they do insure that the student is an active participant in the development of the material presented. Occasionally these exercises, although routine, are lengthy. These instances are noted in the text and, for these exercises, a quick mental review of what is involved should be sufficient for understanding the material. The material presented has proved to be a bit too much for a one-quarter course, and it may be too much for a one-semester undergraduate course. It is possible to choose a subset of the sections as a shorter course. Sections marked with a star may be omitted without missing results needed later on in the book.Context-Free Grammars
Finite-State Acceptors
Finite-State Transducers
Turing Machines and Computable Functions
Universal Turing Machines and the Halting Problem
Turing Machines as Accepting Devices
Nondeterministic Turing Machines
Pushdown Automata
Unsolvable Questions About Context-Free Languages