## Computability, Complexity and Languages: Fundamentals of Theoretical Computer SciencesThis introductory text covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes a minimal background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability. Key Features * Computability theory is introduced in a manner that makes maximum use of previous programming experience, including a "universal" program that takes up less than a page * The number of exercises included has more than tripled * Automata theory, computational logic, and complexity theory are presented in a flexible manner, and can be covered in a variety of different arrangements |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Programs and Computable Functions | 15 |

Primitive Recursive Functions | 32 |

PRC Classes | 34 |

Copyright | |

84 other sections not shown

### Other editions - View all

### Common terms and phrases

algorithm alphabet assume atoms begin belongs blank Blum axiom called Chomsky normal form contains context-free grammar context-free languages context-sensitive context-sensitive grammar context-sensitive language Corollary corresponding define definition derivation tree equation example Exercises Finally finite number finite set G-computable GOTO halts Hence Herbrand Herbrand universe induction hypothesis infinite initial input instruction labeled language Sf Lemma linear bounded automaton literal loop macro expansion ndfa nondeterministic Turing machine NP-complete obtained pair parameter theorem partial function partially computable function Post word Post-Turing program predicate primitive recursive function productions program number proof of Theorem prove Theorem pushdown automaton quadruples r.e. set regular language result satisfiable scanned Section semi-Thue process sentence sequence set of clauses simply simulate stack statement string subset tape configuration terminals Theorem 3.1 transition function true truth-functionally unsatisfiable unsolvable variables W-sentence word problem write