scientific article; zbMATH DE number 3860410
AFL theoryambiguityChomsky hierarchyclosure propertiescomplexity theorycontext-free grammarsdecidabilitydeterministic languagesfinite automatagrammar formsL systemsmorphic representationsnormal formsParikh mappingparsingpure grammarspushdown automatasyntax analysisTuring machines
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Theory of compilers and interpreters (68N20) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)
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.
- String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
- scientific article; zbMATH DE number 3913703 (Why is no real title available?)
- scientific article; zbMATH DE number 3915649 (Why is no real title available?)
- scientific article; zbMATH DE number 4035187 (Why is no real title available?)
- scientific article; zbMATH DE number 4070361 (Why is no real title available?)
- scientific article; zbMATH DE number 50943 (Why is no real title available?)
- Characterization of language learning front informant under various monotonicity constraints
- The triple-pair construction for weighted \(\omega\)-pushdown automata
- scientific article; zbMATH DE number 3194104 (Why is no real title available?)
- The Triple-Pair Construction for Weighted ω-Pushdown Automata
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)