| |
Description: 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.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.ISBN - 9789380108254
|
| |
Pages : 240
|