Introduction to the Theory of ComputationDiscusses such topics as: regular languages; contextfree languages; ChurchTuring thesis; decidability; reducibility; the recursion theorem; time complexity; space complexity; and provable intractability. 
What people are saying  Write a review
User ratings
5 stars 
 
4 stars 
 
3 stars 
 
2 stars 
 
1 star 

Review: Introduction to the Theory of Computation
User Review  Nirbhai Singh  GoodreadsOne of the best writings on computability and complexity theory. And authors chaste way of putting things upfront, just adds to the already whooping brilliance of this text. Read full review
Review: Introduction to the Theory of Computation
User Review  Lewis Cawthorne  GoodreadsHad to shelve this about a third in to focus on classes, but looking forward to finishing it. Read full review
Contents
Automata and Languages  29 
ContextFree Languages  81 
Computability Theory  111 
Copyright  
5 other sections not shown
Common terms and phrases
accepting computation history alphabet arrows automata binary Boolean called Chomsky normal form circuit clause complexity concatenation configuration construct contains contextfree grammar contextfree language convert corresponding decidable language define describe deterministic diagram directed graph domino edges elements empty stack empty string encoding enumerable equivalent example finite automaton following figure formal definition GNFA graph G halts Hamiltonian path HAMPATH induction input string input symbol integers labeled length machine accepts mapping reducibility match mathematical nodes nondeterminism nondeterministic finite nondeterministic finite automaton nondeterministic Turing machine notation NPcomplete output pair parse tree polynomial polynomial time algorithm polynomial time reducible problem of testing programming PROOF IDEA prove pumping lemma pushdown automaton recursion theorem regular expression regular languages reject rule running satisfying assignment Scan sequence simulate singletape Stage steps SUBSETSUM substring tape theory of computation transition function true undecidable variable write