Introduction to the theory of computation

Front Cover
PWS Pub. Co., Jan 1, 1996 - Computers - 239 pages
22 Reviews
Discusses such topics as: regular languages; context-free languages; Church-Turing thesis; decidability; reducibility; the recursion theorem; time complexity; space complexity; and provable intractability

From inside the book

What people are saying - Write a review

User ratings

5 stars
15
4 stars
6
3 stars
0
2 stars
1
1 star
0

Review: Introduction to the Theory of Computation

User Review  - Jeremy Frens - Goodreads

For 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 - Goodreads

I 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

Bibliographic information