Elements of the Theory of ComputationLewis and Papadimitriou present this long awaited Second Edition of their best-selling theory of computation. The authors are well-known for their clear presentation that makes the material accessible to a a broad audience and requires no special previous mathematical experience. KEY TOPICS: In this new edition, the authors incorporate a somewhat more informal, friendly writing style to present both classical and contemporary theories of computation. Algorithms, complexity analysis, and algorithmic ideas are introduced informally in Chapter 1, and are pursued throughout the book. Each section is followed by problems. |
Contents
Introduction | 1 |
Finite Automata | 55 |
Contextfree Languages | 113 |
Copyright | |
5 other sections not shown
Other editions - View all
Common terms and phrases
accepted algorithm alphabet apply automata binary bounded called chapter clauses closed closure complete computation configuration Consider construction contains context-free grammar context-free languages corresponding decides defined definition derivation described deterministic finite automaton directed easy edges element enumerable equivalent exactly example fact Figure final finite automaton formal function given graph halts Hamilton cycle head induction infinite initial input input string instance integer introduced language least length move natural nodes nondeterministic finite NP-complete operation pair parse path polynomial possible problem proof prove pushdown automaton recall recursive reduction regular expressions relation represented result rule SATISFIABILITY sequence Show shown simple simulated solution square stack starting steps string subset Suppose symbol tape Theorem tiling transitions tree Turing machine write