## Elements of the Theory of ComputationThis the Second Edition of Lewis and Papadimtriou's best-selling theory of computation text. In this substantially modified edition, the authors have enhanced the clarity of their presentation by making the material more accessible to a broader undergraduate audience with no special mathematical experience. For example, long proofs have been simplified and/or truncated, with their more technical points delegated to exercises, advanced material is presented in an informal and friendly manner, and problems follow each section to check student comprehension. The book continues to comprise a mathematically sound introduction to the classical and contemporary theory of computation, and provide deep insights into the fundamental paradigms of computer science. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

Finite Automata | 55 |

Contextfree Languages | 113 |

Copyright | |

5 other sections not shown

### Common terms and phrases

2-SATISFIABILITY access Turing machine AfP-complete alphabet automata binary relation Boolean formula called chapter clauses concatenation configuration Consider construction contains context-free grammar context-free languages corresponding defined definition denoted derivation deterministic finite automaton deterministic pushdown automaton directed graph edges element encoding equivalence classes equivalence relation EXACT COVER example exponential final finite set formal Given a Turing grammar G Hamilton cycle INDEPENDENT SET initial input string input symbol instance integer Intuitively Kleene star language accepted leftmost Lemma length mathematical natural numbers nondeterministic finite automaton nondeterministic Turing machine nonterminal output pair parse tree PARTITION path polynomial-time primitive recursive Problems for Section proof of Theorem prove random access Turing recall recursive functions recursively enumerable languages reflexive regular expressions regular languages representation result rule SATISFIABILITY scanned second tape semidecided sequence Show simulated solution stack subproblem subset Suppose tape square transitive closure TRAVELING SALESMAN PROBLEM truth assignment undecidable variables