Preface
Over the past twenty years, automata and formal languages have become the
standard introductory theory course in both the undergraduate and grad-
uate curricula of computer science. The subjects studied in such a course
include automata theory, formal languages, and models of computation. For
a more advanced graduate course, computability theory and computational
complexity theory are also covered. Whereas these materials are fundamental
in many different areas of computer science, this course also offers a unique
opportunity for students to learn various mathematical tools to deal with
nonstandard, abstract objects.
This book is designed for such a course, with the emphasis on problem
solving. It is commonly recognized that the best, if not the only, way to
learn a mathematics subject is through extensive problem-solving experience.
By attacking the problems directly, one not only learns techniques and tools
to solve the problems, but also consolidates understanding of the underlying
concepts. Theory of computation is, by nature, an abstract discipline, and
the problem-solving approach appears to be most helpful.
In this book, we collected a rich variety of examples, ranging from elemen-
tary questions about basic definitions and concepts, to advanced ones that
employ more sophisticated mathematical tools. The proof ideas and tech-
niques are usually explained in a constructive way, often omitting the routine
induction proofs. However, for more difficult questions, the complete, rigorous
proofs are also presented. A star sign (*) next to an example or an exercise
indicates that it is a more advanced question, and may be skipped in the first
reading.
Because the emphasis of the book is problem solving, we only include
the most common topics in theory of computation: finite-state automata,
context-free grammars, Turing machines, recursive and recursively enumer-
able languages, complexity classes, and NP-completeness. In particular, for
vii