T
Chapter 1
Introduction to
the Theory of
Computation
he subject matter of this book, the theory of computation, includes
several topics: automata theory, formal languages and grammars,
computability, and complexity. Together, this material constitutes the
theoretical foundation of computer science. Loosely speaking we can
think of automata, grammars, and computability as the study of what
can be done by computers in principle, while complexity addresses what can be
done in practice. In this book we focus almost entirely on the first of these
concerns. We will study various automata, see how they are related to languages
and grammars, and investigate what can and cannot be done by digital
computers. Although this theory has many uses, it is inherently abstract and
mathematical.
Computer science is a practical discipline. Those who work in it often have a
marked preference for useful and tangible problems over theoretical speculation.
This is certainly true of computer science students who are concerned mainly
with difficult applications from the real world. Theoretical questions interest
them only if they help in finding good solutions. This attitude is appropriate,
since without applications there would be little interest in computers. But given
this practical orientation, one might well ask “why study theory?”
The first answer is that theory provides concepts and principles that help us
understand the general nature of the discipline. The field of computer science
includes a wide range of special topics, from machine design to programming.
The use of computers in the real world involves a wealth of specific detail that
must be learned for a successful application. This makes computer science a
very diverse and broad discipline. But in spite of this diversity, there are some
common underlying principles. To study these basic principles, we construct