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  Jose Vieitez  GoodreadsReally does a great job at bringing high level theories down to the basics, especially in the first half of the book. Eventually, though, the level of complication of proofs (maybe just for me) got ... Read full review
Review: Introduction to the Theory of Computation
User Review  Umang Kumar  Goodreadsthis is the best book Read full review
Contents
Automata and Languages  29 
ContextFree Languages  81 
Computability Theory  111 
Copyright  
5 other sections not shown
Other editions  View all
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