scientific article; zbMATH DE number 3860410

From MaRDI portal
Publication:3327730





The first version of this book by the second author (1969; Zbl 0204.318) is together with the first version of the book by \textit{J. E. Hopcroft} and \textit{J. D. Ullman} Formal languages and their relation ot automata (1969; Zbl 0196.017) really the first attempt to present in one volume all the fundamentals of automata and formal languages: different types of generative and accepting devices. Previous books dealt with some more specialized topics, such as finite automata or context-free grammars. This reviewer liked the first version of this book very much, and used it both in many courses and as a source of reference. In spite of the reliability of the proofs, the material was still presented in a fashion easy to read. The first version was written by Maurer alone. The new, thoroughly updated and revised version is written by Bucher alone - apart from some consulting sessions with both authors present. From everything I have been able to observe so far, it seems to me that the new version, although much more comprehensive, has all the desirable features of the old one. Moreover, the topics added to the new version are not just added there but are treated in a really professional way. Major ones among the new topics are complexity theory, L systems, pure grammars, AFL theory, grammar forms, syntax analysis and normal forms. - I now give a brief description of the four main sections of the new version under review. After a brief introductory section with the basics of sets, monoids and languages, the first real section deals with the Chomsky hierarchy, pure grammars, L systems and grammar forms. Some arguments are very nice, cf. pp. 30 and 58-60. On the latter pages it is explained why a widely used construction is, in fact, wrong. The use of the operation of substitution is very efficient in proofs concerning closure properties. The notation of AFL theory is somewhat unusual. The second section (automata and machines) deals with finite automata, pushdown automata, Turing machines, and machine oriented (and also general) complexity. The final section is concerned with more advanced topics: deterministic languages, ambiguity, (i,j,k) normal forms for context-free grammars (the proof is carefully presented and gives also an upper bound on the length of terminal words appearing on right sides of the productions), basics of parsing algorithms, morphic representations, Parikh mapping and decidability. Altogether a very useful book, both for teaching and a source of basic reference. Since the book has no exercises, it would be a good idea to publish a smaller companion volume of exercises - perhaps some of them with solutions.












This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3327730)