Automata and computability

This book is an excellent textbook covering the classical results on automata and computability. It is based on courses given by the author; therefore it is not divided into chapters, subchapters etc. but in 39 lectures presenting the basic notions and facts and 11 supplementary lectures on advanced topics. The book is very well written and very well readable with respect to motivation, formalization and proofs. The author starts with the intuitive ideas of concepts and methods, given then the formal definitions and proofs; e.g. the half of a lecture is used to present the idea of the pumping lemma or the subset construction and then a complete formal proof is given in the following lecture. The concepts and methods are illustrated by well chosen examples. The historical remarks at the end of some lectures (or given in the text) are very interesting. The lectures are completed by homeworks and exercises of different levels of difficulty (approx. a seventh of the book), hints for and solutions of selected exercises. The Homeworks and exercise allow to check the understanding of the subject but they also add a lot of results and knowledge. Besides two lectures giving the idea and the aim of the book and some notation from set theory and algebra the book is divided into three parts. The first one considers finite automata and regular sets. It starts with the definition of deterministic finite automata and regular sets as sets accepted by such automata. It gives further characterization of regular sets by nondeterministic finite automata, two-way deterministic finite automata, regular expressions and Myhill-Nerode relations (the characterization by right-linear grammars is given as an exercise later), presents the basic properties of regular sets as closure properties with respect to operations, a pumping lemma and relations to pattern matching, discusses the minimization of deterministic and nondeterministic finite automata and considers a generalization to finite automata on terms. The second part starts with the definition of context-free grammars and languages and gives some normal form results and pumping lemmas for them. Then (nondeterministic) push-down automata are introduced and their relation to context-free languages via different types of acceptance (final states, empty stack, etc.) is presented. One lecture discusses deterministic push-down automata. Moreover, parsing and the Cocke-Younger-Kasami algorithm for it, closure properties, the Chomsky-Schützenberger theorem characterizing context-free languages by parenthesis languages, homomorphisms and intersections by regular sets and the Parikh's theorem on the semilinearity of context-free languages are given. The third part addresses effective computability. Turing machines are given as the basic model for the formalization of effective computability. Variations of the basic model of a Turing machine, Post systems, type-0 grammars, \(\mu\)-recursive functions, the \(\lambda\)-calculus and while programs as equivalent approaches are considered. Diagonalization, reduction and Rice's theorem are presented as methods in order to get undecidability results. One lectures contains undecidable problems for context-free languages, and another one discussed relative computations and hardness and completeness. Moreover, Gödel's incompleteness theorem is studied in three lectures.

Recommendations

Cited in

(only showing first 100 items - show all)

This page was built for publication: Automata and computability

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