Introduction to Automata Theory, Languages, and Computation

Last updated
Introduction to Automata Theory, Languages, and Computation
Introduction to Automata Theory, Languages, and Computation.jpg
Cover of the Cinderella Book (1979 edition)
Author John Hopcroft and Jeffrey Ullman
CountryUSA
LanguageEnglish
Subject Computer science
Publisher Addison-Wesley
Publication date
1979
Media typePrint
ISBN 0-201-02988-X
OCLC 4549363
629.8/312
LC Class QA267 .H56

Introduction to Automata Theory, Languages, and Computation is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later editions beginning in 2000.

Contents

Nickname

The Jargon File records the book's nickname, Cinderella Book, thusly: "So called because the cover depicts a girl (putatively Cinderella) sitting in front of a Rube Goldberg device and holding a rope coming out of it. On the back cover, the device is in shambles after she has (inevitably) pulled on the rope." [1]

Edition history and reception

The forerunner of this book appeared under the title Formal Languages and Their Relation to Automata in 1968. Forming a basis both for the creation of courses on the topic, as well as for further research, that book shaped the field of automata theory for over a decade, cf. (Hopcroft 1989).

Formal Languages and Their Relation to Automata appeared in 1968, with an inornate cover. Hopcroft-ullman-old.jpg
Formal Languages and Their Relation to Automata appeared in 1968, with an inornate cover.

The first edition of Introduction to Automata Theory, Languages, and Computation was published in 1979, the second edition in November 2000, and the third edition appeared in February 2006. Since the second edition, Rajeev Motwani has joined Hopcroft and Ullman as the third author. Starting with the second edition, the book features extended coverage of examples where automata theory is applied, whereas large parts of more advanced theory were taken out. While this makes the second and third editions more accessible to beginners, it makes it less suited for more advanced courses. The new bias away from theory is not seen positively by all: As Shallit quotes one professor, "they have removed all good parts." (Shallit 2008).

The first edition in turn constituted a major revision of a previous textbook also written by Hopcroft and Ullman, entitled Formal Languages and Their Relation to Automata. It was published in 1968 and is referred to in the introduction of the 1979 edition. In a personal historical note regarding the 1968 book, Hopcroft states: "Perhaps the success of the book came from our efforts to present the essence of each proof before actually giving the proof" (Hopcroft 1989). Compared with the forerunner book, the 1979 edition was expanded, and the material was reworked to make it more accessible to students, cf. (Hopcroft 1989). This gearing towards understandability at the price of succinctness was not seen positively by all. As Hopcroft reports on feedback to the overhauled 1979 edition: "It seems that our attempts to lower the level of our presentation for the benefit of students by including more detail and explanations had an adverse effect on the faculty, who then had to sift through the added material to outline and prepare their lectures" (Hopcroft 1989).

Still, the most cited edition of the book is apparently the 1979 edition: According to the website CiteSeerX, over 3000 scientific papers freely available online cite this edition of the book. [2]

See also

Related Research Articles

<span class="mw-page-title-main">Context-free grammar</span> Type of formal grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the form

In formal language theory, a context-free language (CFL), also called a Chomsky type-2 language, is a language generated by a context-free grammar (CFG).

In formal language theory, a context-free grammar, G, is said to be in Chomsky normal form if all of its production rules are of the form:

<span class="mw-page-title-main">Finite-state machine</span> Mathematical model of computation

A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.

In theoretical computer science and formal language theory, a regular language is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science.

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

<span class="mw-page-title-main">Alfred Aho</span> Canadian computer scientist

Alfred Vaino Aho is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming.

<span class="mw-page-title-main">John Hopcroft</span> American computer scientist (born 1939)

John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is a professor emeritus at Cornell University, co-director of the Center on Frontiers of Computing Studies at Peking University, and the director of the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University.

In theoretical computer science, a discrete system is a system with a countable number of states. Discrete systems may be contrasted with continuous systems, which may also be called analog systems. A final discrete system is often modeled with a directed graph and is analyzed for correctness and complexity according to computational theory. Because discrete systems have a countable number of states, they may be described in precise mathematical models.

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree. Every non-empty context-free language admits an ambiguous grammar by introducing e.g. a duplicate rule. A language that only admits ambiguous grammars is called an inherently ambiguous language. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however.

Jeffrey David Ullman is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers, theory of computation, data structures, and databases are regarded as standards in their fields. He and his long-time collaborator Alfred Aho are the recipients of the 2020 Turing Award, generally recognized as the highest distinction in computer science.

In computer science, a linear grammar is a context-free grammar that has at most one nonterminal in the right-hand side of each of its productions.

In automata theory, a deterministic pushdown automaton is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.

Indexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automata.

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs.

<span class="mw-page-title-main">Rajeev Motwani</span> Indian computer scientist (1962–2009)

Rajeev Motwani was an Indian American professor of Computer Science at Stanford University whose research focused on theoretical computer science. He was a special advisor to Sequoia Capital. He was a winner of the Gödel Prize in 2001.

<span class="mw-page-title-main">DFA minimization</span> Task of transforming a deterministic finite automaton

In automata theory, DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory.

<span class="mw-page-title-main">Counter automaton</span>

In computer science, more particular in the theory of formal languages, a counter automaton, or counter machine, is a pushdown automaton with only two symbols, and the initial symbol in , the finite set of stack symbols.

In formal language theory and pattern matching, alternation is the union of two sets of strings, or equivalently the logical disjunction of two patterns describing sets of strings.

The union theorem is a result from the 60s in computational complexity theory. It was published in 1969 by Ed McCreight and Albert Meyer.

References

  1. "Cinderella Book" . Retrieved July 22, 2020.
  2. "CiteSeerX Most Cited Computer Science Citations". Archived from the original on Sep 21, 2022. Retrieved May 20, 2009.