John E. Hopcroft, Rajeev Montwani, Jeffrey D. Ullman,
Introduction to Automata Theory, Languages, and Computation
Addison Wesley, Boston, 2001
Hardcover, pp-521, plus XIX, USA $ 66,99
ISBN 0-201-44124-1
http://www.pearsoneduc.com

In general about book

Too often, computer science students have a limited understanding of automata theory as a study of abstract computing devices, little theoretical background of formal languages in which they express some important applications such as, for example, compilers, and minimal knowledge concerning complexity of computation. Recognizing the above mentioned needs the authors have written a significant contribution to the academic arena, a book which will undoubtedly enrich the theory of automata and formal languages. The book contains eleven chapters and Index.

Chapter content

Chapter 1 is an introduction. It begins with discussions related to automata theory, continues with survey of proof techniques (deductive proofs, proofs by contradiction, proofs by induction), and ends with definitions of terms that pervade the theory of automata (alphabets, strings, and languages). Chapter 2 covers the class of languages called regular languages. The topics discussed here are informal picture of finite automata (FA), deterministic and nondeterministic FAs, an application of type text search, and FA with epsilon-transitions. The study of regular languages continues in Chapter 3. Notation called regular-expressions is involved. Principles of regular-expressions in several software systems are given. Several important properties, such as closure properties and decision properties, of regular languages are discussed in Chapter 4. Chapter 5 deals with context-free grammar notation and shown how grammars define languages. In addition details concerning parse trees, context-free grammars and ambiguity in grammars and languages are discussed. Chapter 6 defines automaton-like notation called pushdown-automaton. Two different versions of pushdown-automaton are discussed: One that accepts by entering an accepted state, and another that accepts by emptying stack. Properties of context-free languages (CFLs) are covered in Chapter 7. Included in this chapter are sections that deal with pumping-lemma, and closure and decision properties of CFLs. Chapter 8 introduces Turing Machines (TMs). Details concerning programming techniques for TMs, extension to basic TM, restricted TMs, and comparison between TM and common sort of computer are given. In Chapter 9 the authors use the TM to develop a theory of undecidable problems, that is, problems that no computer can solve. Chapter 10 deals with computational complexity, concretely with the theory of intractability, i.e. techniques for showing problems not to be solvable in polynomial time. Finally, additional classes of problems are considered in Chapter 11.

Useful for senior level mathematically inclined students

Generally speaking, this clearly written book is a good instructional text for advanced under/graduate students of CS field of specialization. To make best use of this book a reader must be familiar with discrete mathematics, programming techniques, data structures and compilers. The organization of the chapters follows an identical pattern: The chapter begins with a brief introduction, then follows an analysis of the main theme, after that the chapter summary which provides a short and clear definition of the main notions involved in the current chapter, and ends with references. In addition at the end of almost every section, within the chapter, numerous unsolved exercises are given. Indeed, I feel that this book is a valuable contribution to the literature in the field of theory of automata and formal languages, and therefore: I highly recommend it.