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  Shawn  GoodreadsI recently took a Finite Automata course in which we actually only covered about half of the material presented in the book. It was very wellwritten and for the most part pretty easy to follow. I'm ... Read full review
Review: Introduction to the Theory of Computation
User Review  Captain Hampton  GoodreadsOne of the texts used for a computational complexity class I had quite a while ago. It's a bit less dense than some other texts on the subject, but still manages to get into many of the core bits of computational complexity theory. Ideal text for an undergraduate course on the subject. 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 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 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