Introduction to the Theory of Computation

Front Cover
PWS Publishing Company, 1996 - Computers - 239 pages
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

Contents

Formal definition of a nondeterministic finite automaton
1
Proof by construction
19
Regular Languages
29
Copyright

8 other sections not shown

Other editions - View all

Common terms and phrases

Bibliographic information