Introduction to Languages and the Theory of Computation,3E [Special Indian Edition] Information Center: Table of Contents


		Preface Salient Features Table of Contents About the Author Queries and Feedback Buy the Book



	Student Edition
	Instructor Edition

Introduction to Languages and the Theory of Computation,3E [Special Indian Edition]

John Martin, North Dakota State University

ISBN: 0070660484
Copyright year: 2007

Preface ix

Introduction xi

P A R T I

Mathematical Notation and Techniques 1

C H A P T E R 1
Basic Mathematical Objects 3

1.1 Sets    3
1.2 Logic    9
1.3 Functions    17
1.4 Relations    22
1.5 Languages    28
Exercises    32
More Challenging Problems    39

C H A P T E R 2
Mathematical Induction and Recursive Definitions 43

2.1 Proofs    43
2.2 The Principle of Mathematical Induction    48
2.3 The Strong Principle of Mathematical Induction    55
2.4 Recursive Definitions    58
2.5 Structural Induction    66
Exercises    72
More Challenging Problems    77

P A R T II

Regular Languages and Finite Automata 83

C H A P T E R 3
Regular Expressions and Finite Automata 85

3.1 Regular Languages and Regular Expressions    85
3.2 The Memory Required to Recognize a Language    90
3.3 Finite Automata    95
3.4 Distinguishing One String from Another    105
3.5 Unions, Intersections, and Complements    109
Exercises    112
More Challenging Problems    118

C H A P T E R 4
Nondeterminism and Kleene's Theorem 123

4.1 Nondeterministic Finite Automata    123
4.2 Nondeterministic Finite Automata with Λ-Transitions    133
4.3 Kleene's Theorem    145
Exercises    156
More Challenging Problems    164

C H A P T E R 5
Regular and Nonregular Languages 168

5.1 A Criterion for Regularity    168
5.2 Minimal Finite Automata    175
5.3 The Pumping Lemma for Regular Languages    180
5.4 Decision Problems    186
5.5 Regular Languages and Computers    189
Exercises    191
More Challenging Problems    196

P A R T III

Context-Free Languages and Pushdown Automata 201

C H A P T E R 6
Context-Free Grammars 203

6.1 Examples and Definitions    203
6.2 More Examples    210
6.3 Regular Grammars    217
6.4 Derivation Trees and Ambiguity    220
6.5 An Unambiguous CFG for Algebraic Expressions    226
6.6 Simplified Forms and Normal Forms    232
Exercises    240
More Challenging Problems    247

C H A P T E R 7
Pushdown Automata 251

7.1 Introduction byWay of an Example    251
7.2 The Definition of a Pushdown Automaton    255
7.3 Deterministic Pushdown Automata    260
7.4 APDACorresponding to a Given Context-Free Grammar    265
7.5 A Context-Free Grammar Corresponding to a Given PDA    273
7.6 Parsing    280
Exercises    290
More Challenging Problems    295

C H A P T E R 8
Context-Free and Non-Context-Free Languages 297

8.1 The Pumping Lemma for Context-Free Languages    297
8.2 Intersections and Complements of Context-Free Languages    306
8.3 Decision Problems Involving Context-Free Languages    311
Exercises    312
More Challenging Problems    314

P A R T IV

Turing Machines and Their Languages 317

C H A P T E R 9
Turing Machines 319

9.1 Definitions and Examples    319
9.2 Computing a Partial Function with a Turing Machine    328
9.3 Combining Turing Machines    332
9.4 Variations of Turing Machines: Multitape TMs    337
9.5 Nondeterministic Turing Machines    341
9.6 Universal Turing Machines    347
9.7 Models of Computation and the Church-Turing Thesis    352
Exercises    354
More Challenging Problems    361

C H A P T E R 10
Recursively Enumerable Languages 365

10.1 Recursively Enumerable and Recursive    365
10.2 Enumerating a Language    368
10.3 More General Grammars    371
10.4 Context-Sensitive Languages and the Chomsky Hierarchy    380
10.5 Not All Languages are Recursively Enumerable    387
Exercises    397
More Challenging Problems    401

P A R T V

Unsolvable Problems and Computable Functions 405

C H A P T E R 11
Unsolvable Problems 407

11.1 A Nonrecursive Language and an Unsolvable Problem    407
11.2 Reducing One Problem to Another: The Halting Problem    411
11.3 Other Unsolvable Problems Involving TMs    416
11.4 Rice's Theorem and More Unsolvable Problems    419
11.5 Post's Correspondence Problem    422
11.6 Unsolvable Problems Involving Context-Free Languages    430
Exercises    436
More Challenging Problems    439

C H A P T E R 12
Computable Functions 442

12.1 Primitive Recursive Functions    442
12.2 Primitive Recursive Predicates and Some Bounded Operations    451
12.3 Unbounded Minimalization and µ-Recursive Functions    459
12.4 Gödel Numbering    461
12.5 All Computable Functions Are µ-Recursive    465
12.6 Nonnumeric Functions, and Other Approaches to Computability    470
Exercises    474
More Challenging Problems    477

P A R T VI

Introduction to Computational Complexity 479

C H A P T E R 13
Measuring and Classifying Complexity 481

13.1 Growth Rates of Functions    481
13.2 Time and Space Complexity of a Turing Machine    486
13.3 Complexity Classes    492
Exercises    497
More Challenging Problems    499

C H A P T E R 14
Tractable and Intractable Problems 500

14.1 Tractable and Possibly Intractable Problems: P and NP    500
14.2 Polynomial-Time Reductions and NP-Completeness    506
14.3 Cook's Theorem    510
14.4 Some Other NP-Complete Problems    517
Exercises    522
More Challenging Problems    524

References    527
Bibliography    529
Index of Notation    531
Index    535

To obtain a lecturer login to the Online Learning Centres, ask your local sales representative. If you're a lecturer thinking about adopting this textbook, request a complimentary copy for review.