05970650

b

05970650 Linz, Peter An introduction to formal languages and automata. With CD-ROM. 5th ed. Sudbury, MA: Jones \& Bartlett Learning (ISBN 978-1-4496-1552-9/hbk). xiii, 437~p. \$~170.95 (2012). 2012 Sudbury, MA: Jones \& Bartlett Learning EN formal languages regular languages context-free languages grammars finite automata pushdown automata Turing machines computability computational complexity Zbl 1230.68010 This book is designed as a text for an undergraduate computer science course on automata, formal languages and computability. As prerequisites the author lists some higher-level programming language, the fundamentals of algorithms and data structures, and a discrete mathematics course, but the computer science knowledge is needed mainly for some of the exercises rather than for understanding the main text. As can be seen from the following review of the contents, the material covered is mostly what one would expect. Chapter 1 recalls some basic mathematical notions and introduces on a general level the ideas of formal languages, grammars and automata. Chapters 2, 3 and 4 cover the elementary theory of finite automata, regular languages and type 3 grammars. This includes deterministic and nondeterministic finite automata, Kleene's theorem, the pumping lemma, several closure properties of the family of regular languages, and the most basic decidability results. Chapters 5 to 8 deal with context-free grammars and pushdown automata. Again, the most fundamental material is included: derivations and derivation trees, the idea of parsing and ambiguity, Chomsky and Greibach normal forms, the equivalence of pushdown automata and context-free grammars, deterministic context-free languages, the basic pumping lemma, closure properties, and some positive decidability results. No practical parsing methods are discussed. Chapters 9 and 10 offer a light introduction to Turing machines and computability. In addition to the basic model, several variants of the Turing machine are mentioned. Turing machines as devices for computing functions naturally precede the introduction of the notion of Turing-computability and Turing's thesis. Chapter 10 concludes with universal Turing machines and linear bounded automata. The Chomsky hierarchy, completed with the families of recursive and deterministic context-free languages, is presented in Chapter 11. In Chapter 12 the notions of decidability and computability are formalized in terms of Turing machines, and the undecidability of the Turing machine halting problem and the Post correspondence problem is shown in the usual manner. These results are then used for proving the undecidability of some problems concerning formal languages. In Chapter 13, recursive functions, Post systems, matrix grammars, Markov algorithms and L-systems are briefly described as further models of computation. Chapter 14 contains an overview of computational complexity. Appendix A introduces Mealy and Moore machines (but not generalized sequential machines as one could have expected). Appendix B advertises the software package JFLAP, a tool for working with grammars and automata. The package comes with the book on a CD-ROM. The presentation could be described as semi-rigorous. The formal definitions and the constructions used in proofs are generously illustrated by examples, but the most technical parts of the proofs are omitted or left as exercises. This approach appears quite appropriate in a book like this, and it works well especially in the chapters on regular and context-free languages, where most constructions are complete and intuitively understandable, while the remaining technicalities make reasonable exercises. In the later chapters the presentation becomes quite informal and many shortcuts are made. For example, instead of corroborating Turing's thesis by showing that all the various variants of Turing machines and other models of effective computation are equivalent to the basic Turing machine, the thesis is used as an argument in the informal proofs of such equivalences. The book contains very many detailed examples and each section is concluded with an ample selection of exercises, and for many of these solutions or hints are offered. Magnus Steinby (Turku)