Ten years ago the authors undertook to produce a book covering the known material on
formal languages, automata theory, and computational complexity. In retrospect, only a
few significant results were overlooked in the 237 pages. In writing a new book on the
subject, we find the field has expanded in so many new directions that a uniform com
prehensive coverage is impossible. Rather than attempt to be encyclopedic, we have been
brutal in our editing of the material, selecting only topics central to the theoretical
development of the field or with importance to engineering applications.
Over the past ten years two directions of research have been of paramount im
portance. First has been the use of language-theory concepts, such as nondetermimsm and
the complexity hierarchies, to prove lower bounds on the inherent complexity of certain
practical problems. Second has been the application of language-theory ideas, such as
regular expressions and context-free grammars, in the design of software, such as compilers
and text processors. Both of these developments have helped shape the organization of
this book.
