Introducing the Theory of Computation

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.

About the author:

Wayne Goddard –Clemson University

Wayne Goddard is currently as Associate Professor in the School of Computing at Clemson University having previously taught at the Universities of KwaZulu-Natal and Pennsylvania. His research interests are graph theory, algorithms, networks and combinatorics. He received his PhDs from the University of KwaZulu-Natal and the Massachusetts Institute of Technology. He has published over 100 journal and conference papers in many areas of graph theory as well as in graph algorithms, self-stabilizing algorithms, game-playing and ad hoc networks, and is co-author of a textbook on Research Methodology.