An Introduction to Formal Languages and Automata, Fourth Edition provides an excellent presentation of the material that is essential to an introductory theory of computation course. This fourth edition offers expanded and simplified discussions of some of the more difficult ideas and constructions that often frustrate students. The author offers an intuitive motivation for proofs, and avoids excessive mathematical detail, so that students can focus on and understand the underlying detail. New end-of-chapter exercises, varying in degree of difficulty, are designed to illuminate and illustrate key concepts and call on students’ problem-solving ability.

• New to this Edition: • Expanded and simplified discussions of some of the more difficult ideas and constructions such as the pumping lemmas, the “finite automata to regular expression” construction, and the “pushdown to context-free grammar” algorithm • New examples that clearly illustrate the above concepts • An introduction of transition graphs for pushdown automata and Turing machines • Chapter 14 has been expanded, making it suitable for a one or one and a half week discussion of computational complexity • New and revised exercises throughout • Instructor’s guide with solutions manual and instructor’s website available

Introduction to the Theory of Computation / Finite Automata / Regular Languages and Regular Grammars / Properties of Regular Languages / Context-Free Languages / Simplification of Context-Free Grammars and Normal Forms / Pushdown Automata / Properties of Context-free Languages / Turing Machines / Other Models of Turing Machines / A Hierarchy of Formal Languages and Automata / Limits of Algorithmic Computation / Other Models of Computation / An Overview of Computational Complexity / Answers / References / Index.

Undergraduate – Postgraduate Students in Computer Science