Vlll... PREFACE
formal languages, we limit ourselves to the basics in regular and context-free
languages, and omit deterministic context-free languages and various parsing
techniques. For computability theory, our approach is a traditional one: we
use Turing machines as a basic model, and develop the notion of computability
through the rich, flexible language of primitive recursive functions. Compar-
isons with high-level language constructs are also included, when appropriate.
The authors have used this book in a number of different classes. In a one-
semester undergraduate course, we usually cover most of Chapters 1 to 3, and
the first half of Chapter 4, skipping most starred examples. In a two-semester
sequence, starred examples may be covered, and an additional chapter (e.g.,
Chapter 7) may be added. In a more advanced graduate course emphasizing
computability and complexity theory, we typically cover Chapters 4 to 7,
skipping some starred proofs in Chapter 6.
We are grateful to our colleagues and students for their suggestions and
criticism on the earlier drafts of this book. We owe special thanks to Xiu-
zhen Cheng and Dean Kelley, who read the manuscript carefully and made a
number of corrections.
DING-ZHU Du
KER-I Ko