Subroutine 333-334 Subset construction 61-66 Substitution 282-285 Switching circuit 125 Symbol

See Generating symbol, Input symbol, Input symbol, Nullable symbol. Reachable symbol. Stack symbol, Start symbol. Tape symbol, Terminal symbol, Useless symbol

Symbol table 279 Syntactic category See Variable

Tail 238

Tape 318

Tape head 318

Tape symbol 319, 327, 357

Tarjan, R. E. 510

Tautology problem 471

Term 209

Terminal symbol 171, 176 Text search 68-72, 84, 111-113 Theorem 17 There exists

See Quantifier Thompson, K. 123 3SAT 435-436, 445-446, 462 Time complexity 339-340,361-363,

414, 503 Token 109-111 Track 331-333

Transition diagram 48, 223-224,323-326

Transition function 46, 57, 222, 319 See also Extended transition function

Transition table 48-49 Transitive law 160

Traveling salesman problem 419-421,

461-462 Tree 23-25

See also Parse tree Treybig, L. B. 468 Trivial property 388 Truth assignment 426-427 TSP

See Traveling salesman problem Turing, A. M. 1, 318, 323, 366, 411 Turing machine 307, 316-329, 414, 473-474 See also Code, for Turing machine, Halting, of a Turing machine. Las-Vegas Turing machine, Monte-carlo Turing machine, Multihead Turing machine, Multitape Turing machine, Nondeterministic Hjring machine. Randomized Turing machine, Recursively enumerable language. Two-dimensional Turing machine. Universal Turing machine Two-dimensional Turing machine 345 2SAT 437, 446

Ulhnan,J.D. 35, 123, 217, 468,510

Unambiguous grammar

See Ambiguous grammar

Undecidable problem 302,310,367-368,373-374,384, 386-387, 390, 403-408 See also Posts correspondence problem. Rices theorem, Universal language

Union 14, 84, 86, 95, 103, 109, 114-117,132,199,284,382, 425-426

Unit pair 263

Unit production 256, 262-266 Unit-execution-time-scheduling problem 465 Universal language 377-381 Universal Turing machine 357, 377-378

INDEX 521

UNIX regular expreaaione Iflfr-llO

Useless symbol 255-259

Variable 171, 176 W

Word

See String World-wide-web consortiran 217

XML 169, 198 See also DTD

YACC 194-195, 208, 253 Yamada, H. 123 Yield 183

Younger, D. H. 298, 305

Zero-error probabilistic polynomial langut See ZVV ZVV 469-70, 488, 495-97

Preface

In the preface from the 1979 predecessor to this book, Hopcroft and Ullman marveled at the fact that the subject of automata had exploded, compared with its state at the time they wrote their first book, in 1969. Truly, the 1979 book contamed many topics not found in the earlier work and was about twice its size. If you compare this book with the 1979 book, you will find that, like the automobiles of the 1970s, this book is larger on the outside, but smaller on the inside. That sounds like a retrograde step, but we are happy with the changes for several reasons.

First, in 1979, automata and language theory was still an area of active research. A purpose of that book was to encourage mathematically inclined students to make new contributions to the field. Today, there is little direct research in automata theory (as opposed to its applications), and thus Uttle motivation for us to retain the succinct, highly mathematical tone of the 1979 book.

Second, the role of automata and Ijmguage theory has changed over the past two decades. In 1979, automata was largely a graduate-level subject, and we imagined our reader was an advanced graduate student, especially those using the later chapters of the book. Today, the subject is a staple of the undergraduate curriculum. As such, the content of the book must assume less in the way of prerequisites from the student, and therefore must provide more of the background and details of arguments than did the earlier book.

A third change in the environment is that Computer Science has grown to an almost unimaginable degree in the past two decades. While in 1979 it was often a challenge to fill up a curriculum with material that we felt would survive the next wave of technology, today very many subdisciplines compete for the limited amount of space in the undergraduate curriculum.

Fourthly, CS has become a more vocational subject, and there is a severe pragmatism among many of its students. We continue to beheve that aspects of automata theory are essential tools in a variety of new disciplines, and we believe that the theoretical, mind-expanding exercises embodied in the typical automata course retain their value, no matter how much the student prefers to learn only the most immediately monetizable technology. However, to assure a continued place for the subject on the menu of topics available to the computer science student, we believe it is necessary to emphasize the applications