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  Jeremy Frens  GoodreadsFor some reason it feels strange to me to write a review for a textbook here at Goodreads, especially for a textbook I read and used years ago. But I love this book. While I was a college professor ... Read full review
Review: Introduction to the Theory of Computation
User Review  Omesh  GoodreadsI like how the book is divided into three sections: Automata and Languages, Computability Theory and Complexity Theory. The book provides a good introduction to computability and complexity ... 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