Elements of computation theory (Q1010960)

The book is intended as an introduction to the theory of computation mainly for students of computer science, engineering and mathematics. It is planned as a one-semester course for undergraduate students. In the learning process the author emphasizes the development of abstract modeling and rigorous argumentation. The book is self-contained and it stays on the introductory level while working through the main notions and techniques in the theoretical foundations of computing. The book contains basic results of formal languages, automata theory and computability including algorithmic complexity theory (but not cryptography). The chapters contain plenty of examples, exercises, and bibliographic remarks. Many examples are thoroughly studied, and some of the exercises are challenging. Also, some of the exercises have answers and partial solutions at the end of the book. The book is well written and is suitable for an undergraduate course in computer and engineering sciences. For mathematicians the treatment of some of the topics may be too narrow. A more comprehensive study of algebraic notions in computation, such as the theory of syntactic semigroups, are not presented -- although congruences are treated in a gentle way in Section 4.4. The contents of the book are the following: Chapter 1 gives basic mathematical preliminaries on sets and relations together with some counting arguments. Chapters 2 and 3 introduce regular languages and finite automata. The equivalence results involving these notions are proved. The next chapter contains the closure and the structural results of regular languages including minimization of deterministic finite automata. Chapters 5 and 6 introduce the context-free languages, their normal forms, and pushdown automata as an acceptance device. Also, the restrictive pumping lemma is proved in this chapter. Chapter 7 starts the computability studies and introduces various variants of Turing machines. Chapters 8 and 9 concentrate on decision problems and undecidability including Rice's theorem and also concrete undecidable problems. Chapter 10 studies computational complexity. The class NP is defined and NP-completeness is considered. At the end of the book there are answers and hints to selected problems, and a list of references.