Finite automata, their algebras and grammars. Towards a theory of formal expressions. (English) Zbl 0715.68062

New York etc.: Springer-Verlag. XXII, 316 p. DM 138.00 (1989).
The author, Richard Büchi, left this book in an unfinished form before his unexpected death in 1984. The manuscript was edited and brought to publication by Büchi’s longtime collaborator, Dirk Siefkes.
The book presents a rather unified, algebraic style, approach to finite automata and grammars. This approach was inspired by the work of Emil Post on canonical systems, Axel Thue’s work on (what nowadays is called) Thue systems, and by Jesse Wright’s work on finite automata. The book can be divided into two parts: chapters 1 through 5, and chapters 6 and 7.
The first chapter gives a rather thorough exposition of all the prerequisites from algebra and discrete mathematics that are needed to read this book. In chapter 2 through 5 the author shows how the basic concepts and results concerning the structure and behavior of finite automata can be viewed as special cases of fundamental concepts of abstract algebra: homomorphisms, congruence relations, free algebras, etc. In this context, (finite) automata are simply (finite, universal) algebras with unary operations. In chapters 6 and 7 the author drops the restriction to unary algebras and attempts to extend the theory presented in chapters 2-5 to arbitrary algebras. This results in algebraic approaches to theories of tree automata and push-down automata, including a treatment of LR(k) grammars and their relation to parsing.
Reviewer: G.Slutzki


68Q70 Algebraic theory of languages and automata
68Q42 Grammars and rewriting systems
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science