×

Automata and languages. (English) Zbl 0778.68065

Oxford Science Publications. Oxford: Oxford University Press (Clarendon Press),. X, 294 p. £35.00/hbk; £15.00/pbk (1991).
This is a textbook for a general introduction to automata and formal languages. Let us first review briefly the contents of the seven chapters.
Chapter 1 (Mathematical preliminaries) starts with sets, functions and relations, but mainly it is an introduction to semigroups and monoids. Chapter 2 (Automata) treats finite automata and rational languages: deterministic and nondeterministic automata, the Pumping Lemma, rational sets, some closure properties, and Kleene’s theorem. Chapter 3 (The syntactic monoid) complements the previous chapter by introducing syntactic monoids, reduced and minimal automata, and transformation monoids of automata. In Chapter 4 (Languages) general phrase structure grammars are defined, and the correspondence between rational languages and right-linear grammars is shown. Context-free languages are considered briefly, the main result being Chomsky’s normal form theorem. Chapter 5 ( Pushdown automata) introduces pushdown automata and proves that they recognize exactly the context-free languages. Moreover, it contains the Pumping Lemma and examples of non-context-free languages. Also, a few closure properties of the family of CF languages are given. In Chapter 6 ( Turing machines) the basic theory of Turing machines is presented, and the connection with type 0 grammars is shown. In chapter 7 (Varieties) the discussion returns to rational languages. Varieties of finite monoids and varieties of rational languages are considered, Eilenberg’s Variety Theorem is proved and Schützenberger’s characterization of star-free languages is presented. Each chapter ends in a good set of exercises.
The book contains enough material for a full course, but it can also be used for shorter courses. For example, as the author suggestes, one could base on it a course with an algebraic flavour focusing on finite automata, regular languages, syntactic monoids and varieties, or a short general introduction to machines and languages which would omit syntactic monoids and the variety theory. The book should be perfectly suited for attracting mathematics students, for whom it is mainly written, to this important area of modern mathematics. On the other hand, many topics are omitted which usually appear in a course on automata and formal languages offered to computer science students. For example, neither the algorithmic aspects of the theory nor complexity issues are considered at all. The important subject of parsing is bypassed, too. However, also a computer science student would certainly benefit from this book by learning how theorem in this area can be proved rigorously without having to introduce any heavy formal machinery. The exercises are completely solved in a separate section which naturally helps readers using the book for private study.
There are a few slips and omissions, but the exposition is generally very lucid. The concentration on relatively few central concepts and results is also a great pedagogical merit: the main features of the theory become clearly visible and it has been possible to illustrate by examples all important definitions and theorems, and to develop and explain the proofs in sufficient detail.
Reviewer: M.Steinby (Turku)

MSC:

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
PDFBibTeX XMLCite