Introduction to Languages and the Theory of Computation / Edition 4

by John Martin

Overview

Introduction to Languages and the Theory of Computation helps students make the connection between the practice of computing and an understanding of the profound ideas that defines it. The book's organization and the author's ability to explain complex topics clearly make this introduction to the theory of computation an excellent resource for a broad range of upper level students. The author has learned through many years of teaching that the best way to present theoretical concepts is to take advantage of the precision and clarity of mathematical language. In a way that is accessible to students still learning this language, he presents the necessary mathematical tools gently and gradually which provides discussion and examples that make the language intelligible.

Product Details

ISBN-13:	9780073191461
Publisher:	McGraw-Hill Higher Education
Publication date:	02/02/2010
Edition description:	New Edition
Pages:	448
Product dimensions:	7.40(w) x 9.20(h) x 0.90(d)

Table of Contents

I Mathematical Notation and Techniques1 Basic Mathematical Objects 2 Mathematical Induction and Recursive Definitions II Regular Languages and Finite Automata 3 Regular Expressions and Finite Automata 4 Nondeterminism and Kleene's Theorem 5 Regular and Nonregular Languages III Context-Free Languages and Pushdown Automata 6 Context-Free Grammars 7 Pushdown Automata 8 Context-Free and Non-Context-Free Languages IV Turing Machines and Their Languages 9 Turing Machines 10 Recursively Enumerable Languages V Unsolvable Problems and Computable Functions 11 Unsolvable Problems 12 Computable Functions VI Introduction to Computational Complexity 13 Measuring and Classifying Complexity 14 Tractable and Intractable Problems