## Elements of the Theory of ComputationA general, yet comprehensive, introduction to the classical and contemporary 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

User Review - Flag as inappropriate

Its a great book on theory of computation, covering fundamentals, theory, and problems adequately. I am teaching TC through the book to my MCA (PG) students for the last 5 years. Ofcourse, there are minor typos. Kindly put errata of the book on net.

Regards

D J Nagendra Kumar

Associate Professor

Dr. B V raju Inst. of Computer Education

Vishnupur

Bhimavaram-534201.

AP

INDIA

### Contents

FINITE AUTOMATA | 49 |

CONTEXTFREE LANGUAGES | 95 |

TURING MACHINES | 168 |

Copyright | |

6 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 finite set Formally formula F function signs functional form Godel number grammar G halts on input Hamilton cycle head induction hypothesis 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