Elements of the Theory of ComputationA general, yet comprehensive, introduction to the classical and contemporary theory of computation. |
Contents
THE PROPOSITIONAL CALCULUS | 21 |
CONTEXTFREE LANGUAGES | 95 |
Problems | 153 |
Copyright | |
8 other sections not shown
Other editions - View all
Common terms and phrases
1-place a₁ a₂ algorithm alphabet atomic formulas automata B₁ B₂ binary blank C₁ C₂ clause set computation configuration conjunctive normal form construction contains context-free grammar context-free languages countably decides defined definition derivation deterministic finite automaton disjunctive encoding equivalent example Formally formula F function signs Gödel number grammar G head induction hypothesis infinite input string integers K₁ K₂ L₂ leftmost Lemma Let G M₁ M₂ n₂ natural numbers nodes nondeterministic finite automaton nondeterministic Turing machine nonterminal NP-complete occurrence P₁ pair parse tree polynomial polynomial-time predicate calculus predicate sign primitive recursive functions problem proof of Theorem propositional calculus pushdown automaton q₁ quantifiers r₁ regular expression regular languages relation rule S₁ satisfiable scanned second tape Show simulated stack subformulas subset Suppose t₁ tape square third tape tiling tion transformation transitions truth-assignment truth-value Turing-acceptable Turing-computable Turing-decidable u₁ unsatisfiable unsolvable variables w₁ w₂