This text covers all the material essential to an introductory theory of computation course for undergraduate students. The text has a solid mathematical base, and provides precise mathematical statements of theorems and definitions, giving an intuitive motivation for constructions and proofs. Proofs and arguments are clearly stated, without excessive mathematical detail, to help students understand the basic principles. The text is illustrated with integrated examples of new concepts as well as an abundance of exercises to aid in the development of problem solving skills. --This text refers to an out of print or unavailable edition of this title.
1 Introduction to the Theory of Computation 1 2 Finite Automata 37 3 Regular Languages and Regular Grammars 73 4 Properties of Regular Languages 101 5 Context-Free Languages 129 6 Simplification of Context-Free Grammars and Normal Forms 155 7 Pushdown Automata 181 8 Properties of Context-Free Languages 211 9 Turing Machines 229 10 Other Models of Turing Machines 257 11 A Hierarchy of Formal Languages and Automata 285 12 Limits of Algorithmic Computation 311 13 Other Models of Computation 337 14 An Introduction to Computational Complexity 257