## Introduction to the Theory of ComputationDiscusses such topics as: regular languages; context-free languages; Church-Turing thesis; decidability; reducibility; the recursion theorem; time complexity; space complexity; and provable intractability. |

### What people are saying - Write a review

#### LibraryThing Review

User Review - themulhern - LibraryThingThis book is a real gem. A coherent focus is maintained throughout, subjects are introduced in a rational order, and not a word or paragraph is wasted. The assignments at the end of the chapter are ... Read full review

#### LibraryThing Review

User Review - sbloom42 - LibraryThingI read this for a class in the Theory of Computation. The book was very clear and as easy to read as any other theoretical math textbook. 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 context-free grammar context-free 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 NP-complete 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 single-tape Stage steps SUBSET-SUM substring tape theory of computation transition function true undecidable variable write