Elements of the Theory of ComputationA general, yet comprehensive, introduction to the classical and contemporary theory of computation. |
Contents
FINITE AUTOMATA | 49 |
CONTEXTFREE LANGUAGES | 95 |
Problems | 153 |
Copyright | |
8 other sections not shown
Other editions - View all
Common terms and phrases
2-place A V B a₁ a₂ accepts algorithm alphabet atomic formulas automata B₁ B₂ binary C₁ C₂ clause set computation configuration conjunctive normal form construction contains context-free grammar context-free languages countable d₁ decides defined definition derivation deterministic finite automaton disjunctive normal form encoding equivalent example Formally formula F function signs functional form G₂ grammar G halts Hamilton cycle Herbrand expansion infinite input string integers L₂ Lemma Let F Let G literals M₁ M₂ n₂ natural numbers negation nondeterministic Turing machine nonterminal NP-complete number of steps occurrence pair parse tree polynomial polynomial-time predicate calculus predicate sign primitive recursive functions problem proof of Theorem propositional calculus pushdown automaton quantifiers R₁ regular expression relation rule s₁ satisfiable Show simulation subformulas subset Suppose symbol t₁ tape square tiling tion transformation transitions truth-assignment truth-value Turing-acceptable Turing-decidable u₁ unsatisfiable unsolvable variables verifies w₁ write