Introduction to automata theory, languages, and computation. 2nd ed. (English) Zbl 0980.68066

Reading, MA: Addison-Wesley. xiv, 521 p. (2001).
The first edition of this book appeared in (1979; Zbl 0426.68001). Now-a-days the subject is a course for undergraduate students in Engineering and Technology Courses. Taking this aspect into account, the authors have formulated the chapters.
The following is the table of contents of the present edition: 1. Automata: The Method and the Madness; 2. Finite Automata; 3. Regular Expressions and Languages; 4. Properties of regular Languages; 5. Context-Free Grammars and Languages; 6. Pushdown Automata; 7. Properties of Context-Free Languages; 8. Introduction to Turing Machines; 9. Undecidability; 10. Intractable Problems; 11. Additional Classes of Problems.
Each chapter comprises exercises, summary and references. Figures are given to make the understanding clear. The coverage includes Chomsky and Greibach normal forms, Kruskal’s algorithm, Ogden’s lemma, Post’s correspondence problem, pumping lemma, Rice’s theorem, Savitch’s theorem and the travelizer salesman problem.
The following exercises typifies the standard of the problems: 1. Suppose that \(p\) and \(q\) are distinguishable states of a given DFA \(A\) with \(n\) states. As a function of \(n\), what is the tighest upper bound on how. Long the shortest strint that distinguishes \(p\) and \(q\) can be? 2. Design a contxt-free grammar for the language \(\{0^n 1^n:n\geq 1\}\), that is, the set of all strings of one or more \(0\)’s followed by an equal number of \(1\)’s. 3. Design a Turing machine for the language: the set of strings with an equal number of \(0\)’s and \(1\)’s.
Before taking a course on Automata, Formal language and Computation, students should have studied Discrete Mathematics, common data structures and compilers. The get-up and printings are attractive.


68Q45 Formal languages and automata
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science


Zbl 0426.68001