## Elements of the theory of computation |

### What people are saying - Write a review

#### LibraryThing Review

User Review - bnielsen - LibraryThingIndeholder "Preface", "Chapter 1. Sets, Relations and Languages", " 1.1 "If-Then" and its Relatives", " 1.2 Sets", " 1.3 Relations and Functions", " 1.4 Special Types of Binary Relations", " 1.5 ... Read full review

### Contents

FINITE AUTOMATA | 49 |

CONTEXTFREE LANGUAGES | 95 |

CHURCHS THESIS 2 | 222 |

Copyright | |

5 other sections not shown

### Other editions - View all

### Common terms and phrases

2-place 9l(P-complete algorithm alphabet atomic formulas automata binary relation blank clause set computation configuration conjunctive normal form construction contains context-free grammar context-free languages corresponding countably decides defined definition derivation deterministic finite automaton disjunctive normal form encoding equivalent example Formally formula F function signs functional form Godel number grammar G halts on input Hamilton cycle head induction hypothesis infinite input string integers leftmost Lemma Let G mathematical natural numbers nodes nondeterministic finite automaton nondeterministic Turing machine nonterminal notation number of a's number of steps occurrence operation pair parse tree polynomial polynomial-time predicate calculus predicate sign primitive recursive functions problem proof of Theorem propositional calculus pushdown automaton quantifiers reflexive regular expression regular languages satisfiable scanned second tape sequence Show shown in Figure simulated stack subformulas Suppose tape square third tape tiling tion transformation truth-assignment truth-value Turing-acceptable Turing-decidable unsatisfiable unsolvable variables write