Introducing the Theory of Computation

0.0

Introducing the Theory of Computation is the ideal text for any undergraduate, introductory course on formal languages, automata, and computability. The author provides a concise, yet complete, introduction to the important models of finite automata, grammars, and Turing machines, as well as to undecidability and the basics of complexity theory. Numerous problems, varying in level of difficulty, round out each chapter and allow students to test themselves on key topics. Answers to selected exercises are included as an appendix and a complete instructor’s solutions manual is available on the text’s website. Key Features Provides a concise introduction to core topics taught in a single semester Theory of Computation or Automata Theory course. Incorporates an engaging, student-friendly writing style and moves through material at a pace appropriate for undergraduate students. Numerous exercise sets throughout the text allow students to test themselves on the key material at hand before moving on to more difficult topics. Table of Contents Part 1: Regular Languages Chapter 1 Finite Automata A finite automaton has states Building FAs Representing FAs Exercises Chapter 2 Regular Expressions Kleene’s Theorem Applications of REs Chapter 3 Nondeterminism Nondeterministic finite automata What is nondetermination? e-transitions Kleene’s Theorem revisited Conversion from RE to NFA Conversion from NFA to DFA Conversion from FA to RE Exercises Chapter 4 Properties of Regular Languages Closure properties Distinguishable strings The pumping lemma Exercises Chapter 5 Applications of Finite Automata String processing Finite-state machines Statecharts Lexical analysis Exercises Summary Interlude: JFLAP Part II: Context-Free Languages Chapter 6 Context-Free Grammars Productions Further examples Derivative trees and ambiguity Regular languages revisited Exercises Chapter 7 Pushdown Automata A PDA has a stack Nondetermination and further examples Context-free languages Applications of PDAs Exercises Chapter 8 Grammars and Equivalencies Regular grammars The Chomsky hierarchy Usable and nullable variables Conversions from CFG to PDA An alternative representation Conversion from PDA to CFG Properties of Context-free languages Chapter 9 Properties of Context-free Languages Chomsky normal form The Pumping Lemma: Proving languages not context-free exercises Chapter 10 Deterministic Parsing Compilers Bottom-up Parsing Table-driven parser for LSR (1) grammars Construction of an SLR (1) table Guaranteed parsing Exercises Part III: Turing Machines Chapter 11 Turing Machines A turning machine has a tape More examples TM subroutines TMs that do not halt Exercises Chapter 12 Variations of Turning Machines TMs as transducers Variations on the model Multiple tapes Nondeterminism and halting Church’s thesis Universal TMs Exercises Chapter 13 Decidable Problems and Recursive Languages Recursive and recursively enumerable languages Decidable questions Decidable questions about simple models Reasoning about computation Other models Exercises Summary Interlude: Alternative computers Part IV: Undecidability Chapter 14 Diagonalization and the Halting Problem Self-denial Countable sets Diagonalization The halting problem Exercises Chapter 15 More Undecidable Problems Reductions Questions about TMs Other machines Post’s correspondence problem Exercises Chapter 16 Recursive Functions Primitive recursive functions Examples: Functions and predicates Functions that are not primitive recursive Bounded and unbounded minimization Exercises Part V: Complexity Theory Chapter 17 Time Complexity Time Polynomial time Examples Nondetermistic time Certificates and examples P versus NP Exercises Chapter 18 Space Complexity Deterministic space Nondeterministic space Polynomial space Logarithmic space Exercises Chapter 19 NP-Completeness NP-Complete problems Examples Proving NP-Completeness by reduction Exercises Summary Interlude Dealing with hard problems Selected solutions to exercises