Introduction to the theory of computation

Front Cover
PWS Pub. Co., Jan 1, 1996 - Computers - 239 pages
23 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
17
4 stars
5
3 stars
0
2 stars
1
1 star
0

Review: Introduction to the Theory of Computation

User Review  - Shawn - Goodreads

I recently took a Finite Automata course in which we actually only covered about half of the material presented in the book. It was very well-written 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 - Goodreads

One 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

Related books

Contents

Automata and Languages
29
ContextFree Languages
81
Computability Theory
111
Copyright

5 other sections not shown

Common terms and phrases

Bibliographic information