Theory Of Computer Science: Theory, Automata, And Computation is a book that is useful for those who actively pursue the habit of inculcating knowledge in computer science. This comprehensive academic book covers formal computer languages and computation.
The automata theory is the study of abstract machines and their application in solving computational problems. Automata is a major part of this book, and is explained elaborately throughout in easily comprehensible ways.
Besides providing readers with a detailed introduction to the theories related to computer science, this book also fully covers mathematical preliminaries which are essential to computation. The 3rd edition of Theory Of Computer Science: Theory, Automata, And Computation comes updated with the latest breakthroughs made in the rapidly changing field of computer science. This edition has incorporated new chapters and sections on topics such as the NP class of the computational theory and quantum computability.
83 different solved examples have been included as supplementary examples over the course of the book for every chapter, and thus help students in testing their knowledge of the concepts they learn in each chapter. In addition, explanatory solutions have been provided at the end of the book for the questions given towards the conclusion of each chapter. In order to help improve the problem-solving capabilities of students, the author has also made sure that every chapter in this book includes objective-type questions.
The 3rd edition of Theory Of Computer Science: Theory, Automata, And Computation was published by was published by PHI in 2006, and is available as a paperback.
Content – Theory of Computer Science
PROPOSITIONS AND PREDICATES 1-35
1.1 Propositions (or Statements) 1
1.1.1 Connectives (Propositional Connectives
or Logical Connectives) 2
1.1.2 Well-formed Formulas 6
1.1.3 Truth Table for a Well-formed Formula 7
1.1.4 Equivalence of Well-formed Formulas 9
1.1.5 Logical Identities 9
1.2 Normal Forms of Well-formed Formulas 11
1.2.1 Construction to Obtain a Disjunctive Normal
Form of a Given Formula II
1.2.2 Construction to Obtain the Principal
Disjunctive Normal Form of a Given Formula 12
1.3 Rules of Inference for Propositional Calculus
(Statement Calculus) 15
1.4 Predicate Calculus 19
1.4.1 Predicates 19
1.4.2 Well-formed Formulas of Predicate Calculus 21
1.5 Rules of Inference for Predicate Calculus 23
1.6 Supplementary Examples 26
Se(f-Test 31
Exercises 32 Theory of Computer Science
MATHEMATICAL PRELIMINARIES
2.1 Sets, Relations and Functions 36
2.1.1 Sets and Subsets 36
2.1.2 Sets with One Binary Operation 37
2.1.3 Sets with Two Binary Operations 39
2.1.4 Relations 40
2.1.5 Closure of Relations 43
2.1.6 Functions 45
2.2 Graphs and Trees 47
2.2.1 Graphs 47
2.2.2 Trees 49
2.3 Strings and Their Properties 54
2.3.1 Operations on Strings 54
2.3.2 Terminal and Nonterrninal Symbols 56
2.4 Principle of Induction 57
2.4.1 Method of Proof by Induction 57
2.4.2 Modified Method of Induction 58
2.4.3 Simultaneous Induction 60
2.5 Proof by Contradiction 61
2.6 Supplementary Examples 62
Self-Test 66
Exercises 67 Theory of Computer Science
THE THEORY OF AUTOMATA 71-106
3.1 Definition of an Automaton 7]
3.2 Description of a Finite Automaton 73
3.3 Transition Systems 74
3.4 Propeliies of Transition Functions 75
3.5 Acceptability of a String by a Finite Automaton 77
3.6 Nondeterministic Finite State Machines 78
3.7 The Equivalence of DFA and NDFA 80
3.8 Mealy and Moore Models 84
3.8.1 Finite Automata with Outputs 84
3.8.2 Procedure for Transforming a Mealy Machine
into a Moore Machine 85
3.8.3 Procedure for Transforming a Moore Machine
into a Mealy Machine 87
3.9 Minimization of Finite Automata 91
3.9.1 Construction of Minimum Automaton 92
3.10 Supplementary Examples 97
Self-Test 103
Exercises ]04 Theory of Computer Science
FORMAL LANGUAGES
4.1 Basic Definitions and Examples 107
4.1.1 Definition of a Grammar 109
4.1.2 Derivations and the Language Generated by a
Grammar 110
4.2 Chomsky Classification of Languages 120
4.3 Languages and Their Relation 123
4.4 Recursive and Recursively Enumerable Sets 124
4.5 Operations on Languages 126
4.6 Languages and Automata 128
4.7 Supplementary Examples 129
Self-Test 132
Exercises 134
107-135 Theory of Computer Science
REGULAR SETS A~TJ) REGULAR GRAMMARS 136-179
5.1 Regular Expressions 136
5.1.1 Identities for Regular Expressions 138
5.2 Finite Automata and Regular Expressions 140
5.2.1 Transition System Containing A-moves 140
5.2.2 NDFAs with A-moves and Regular Expressions 142
5.2.3 Conversion of Nondeterministic Systems to
Deterministic Systems 146
5.2.4 Algebraic Method Using Arden’s Theorem 148
5.2.5 Construction of Finite Automata Equivalent
to a Regular Expression 153
5.2.6 Equivalence of Two Finite Automata 157
5.2.7 Equivalence of Two Regular Expressions 160
5.3 Pumping Lemma for Regular Sets 162
5.4 Application of Pumping Lemma 163
5.5 Closure Properties of Regular Sets 165
5.6 Regular Sets and Regular Grammars 167
5.6.1 Construction of a Regular Grammar Generating
T(M) for a Given DFA M 168
5.6.2 Construction of a Transition System M Accepting
L(G) for a Given Regular Grammar G 169
5.7 Supplementary Examples 170
Self-Test 175
Exercises 176 Theory of Computer Science
CONTEXT·FREE LANGUAGES
6.1 Context-free Languages and Derivation Trees 180
6.1.1 Derivation Trees 181
6.2 Ambiguity in Context-free Grammars 188
6.3 Simplification of Context-free Grammars
6.3.1 Construction of Reduced Grammars
6.3.2 Elimination of Null Productions
6.3.3 Elimination of Unit Productions
6.4 Normal Forms for Context-free Grammars
6.4.1 Chomsky Normal Form 201
6.4.2 Greibach Normal Form 206
6.5 Pumping Lemma for Context-free Languages
6.6 Decision Algorithms for Context-free Languages
6.7 Supplementary Examples 218
Self-Test 223
Exercises 224 Theory of Computer Science
213
217
PUSHDOWN AUTOMATA 227-266
7.1 Basic Definitions 227
7.2 Acceptance by pda 233
7.3 Pushdown Automata and Context-free Languages 240
7.4 Parsing and Pushdown Automata 251
7.4.1 Top-down Parsing 252
7.4.2 Top-down Parsing Using Deterministic pda’s 256
7.4.3 Bottom-up Parsing 258
7.5 Supplementary Examples 260
Sell Test 264
Exercises 265 Theory of Computer Science
LR(k) GRAMMARS
8.1 LR(k) Grammars 267
8.2 Properties of LR(k) Grammars
8.3 Closure Properties of Languages
8.4 Supplementary Examples 272
Self-Test 273
Erercises 274
TURING MACHINES AND LINEAR BOUNDED
AUTOMATA 277-308
9.1 Turing Machine Model 278
9.2 Representation of Turing Machines 279
9.2.1 Representation by Instantaneous Descriptions 279
9.2.2 Representation by Transition Table 280
9.2.3 Representation by Transition Diagram 281
9.3 Language Acceptability by Turing Machines 283
9.4 Design of Turing Machines 284
9.5 Description of Turing Machines 289 Theory of Computer Science
9.6 Techniques for TM Construction 289
9.6.1 Turing Machine with Stationary Head 289
9.6.2 Storage in the State 290
9.6.3 Multiple Track Turing Machine 290
9.6.4 Subroutines 290
9.7 Variants of Turing Machines 292
9.7.1 Multitape Turing Machines 292
9.7.2 Nondeterministic Turing Machines 295
9.8 The Model of Linear Bounded Automaton 297
9.8.1 Relation Between LBA and Context-sensitive
Languages 299
9.9 Turing Machines and Type 0 Grammars 299
9.9.1 Construction of a Grammar Corresponding to TM 299
9.10 Linear Bounded Automata and Languages 301
9.11 Supplementary Examples 303
Self-Test 307
Exercises 308 Theory of Computer Science
DECIDABILITY AJ\i’D RECURSIVELY El\TU1\fERABLE
LANGUAGES 309-321
10.1 The Definition of an Algorithm 309
10.2 Decidability 310
10.3 Decidable Languages 311
10.4 Undecidable Languages 313
10.5 Halting Problem of Turing Machine 314
10.6 The Post Correspondence Problem 315
10.7 Supplementary Examples 317
Self-Test 319
Exercises 319 Theory of Computer Science
COMPUTABILITY
11.1 Introduction and Basic Concepts 322
11.2 Primitive Recursive Functions 323
11.2.1 Initial Functions 323
11.2.2 Primitive Recursive Functions Over N
11.2.3 Primitive Recursive Functions Over {a. b}
11.3 Recursive Functions 329
11.4 Partial Recursive Functions and Turing Machines
11.4.1 Computability 332
11.4.2 A Turing Model for Computation
11.4.3 Turing-computable Functions 333
11.4.4 Construction of the Turing Machine That
Can Compute the Zero Function Z 334
11.4.5 Construction of the TUling Machine for ComputingThe Successor Function 335
11.4.6 Construction of the Turing Machine for Computing
the Projection Vi” 336
11.4.7 Construction of the Turing Machine That Can
Perform Composition 338
11.4.8 Construction of the Turing Machine That Can
Perform Recursion 339
11.4.9 Construction of the Turing Machine That Can Perform
Minimization 340
11.5 Supplementary Examples 340
Self-Test 342
Exercises 343 Theory of Computer Science
COMPLEXITY
12.1 Growth Rate of Functions 346
12.2 The Classes P and NP 349
12.3 Polynomial Time Reduction and NP-completeness
12.4 Importance of NP-complete Problems 352
12.5 SAT is NP-complete 353
12.5.1 Boolean Expressions 353
12.5.2 Coding a Boolean Expression 353
12.5.3 Cook’s Theorem 354
12.6 Other NP-complete Problems 359
12.7 Use of NP-completeness 360
12.8 Quantum Computation 360
12.8.1 Quantum Computers 361
12.8.2 Church-Turing Thesis 362
12.8.3 Power of Quantum Computation 363
12.8.4 Conclusion 364
12.9 Supplementary Examples 365
Self-Test 369
Exercises 370 Theory of Computer Science
Answers to Self-Tests
Solutions (or Hints) to Chapter-end Exercises
Further Reading
Index
346-371
351
373-374
375-415
417-418
419-422
Preface – Theory of Computer Science
The enlarged third edition of Thea/}’ of Computer Science is the result of the enthusiastic reception given to earlier editions of this book and the feedback received from the students and teachers who used the second edition for several years, The new edition deals with all aspects of theoretical computer science, namely automata, formal languages, computability and complexity, Very few books combine all these theories and give/adequate examples. This book provides numerous examples that illustrate the basic concepts. It is profusely illustrated with diagrams. While dealing with theorems and algorithms, the emphasis is on constructions. Theory of Computer Science
Each construction is immediately followed by an example and only then the formal proof is given so that the student can master the technique involved in the construction before taking up the formal proof. The key feature of the book that sets it apart from other books is the provision of detailed solutions (at the end of the book) to chapter-end exercises. The chapter on Propositions and Predicates (Chapter 10 of the second edition) is now the first chapter in the new edition. The changes in other chapters have been made without affecting the structure of the second edition. The chapter on Turing machines (Chapter 7 of the second edition) has undergone major changes.
A novel feature of the third edition is the addition of objective type questions in each chapter under the heading Self-Test. This provides an opportunity to the student to test whether he has fully grasped the fundamental concepts. Besides, a total number of 83 additional solved examples have been added as Supplementary Examples which enhance the variety of problems dealt with in the book.
The sections on pigeonhole principle and the principle of induction (both in Chapter 2) have been expanded. In Chapter 5, a rigorous proof of Kleene’s theorem has been included. The chapter on LR(k) grammars remains the same Chapter 8 as in the second edition. Chapter 9 focuses on the treatment of Turing machines (TMs). A new section on high-level description of TM has been added and this is used in later examples and proofs. Some techniques for the construction of TMs have been added in Section 9.6. Theory of Computer Science
The multitape Turing machine and the nondeterministic Turing machine are discussed in Section 9.7. A new chapter (Chapter 10) on decidability and recursively enumerable languages is included in this third edition. In the previous edition only a sketchy introduction to these concepts was given. Some examples of recursively enumerable languages are given in Section 10.3 and undecidable languages are discussed in Section lOA. The halting problem of TM is discussed in Section 10.5. Chapter 11 on computability is Chapter 9 of the previous edition without changes. Chapter 12 is a new chapter on complexity theory and NP-complete problems. Cook’s theorem is proved in detail. A section on Quantum Computation is added as the last section in this chapter. Theory of Computer Science
Although this topic does not fall under the purview of theoretical computer science, this section is added with a view to indicating how the success of Quantum Computers will lead to dramatic changes in complexity theory in the future. The book fulfils the curriculum needs of undergraduate and postgraduate students of computer science and engineering as well as those of MCA courses. Though designed for a one-year course, the book can be used as a onesemester text by a judicious choice of the topics presented. Special thanks go to all the teachers and students who patronized this book over the years and offered helpful suggestions that have led to this new edition. In particular, the critical comments of Prof. M. Umaparvathi, Professor of Mathematics, Seethalakshmi College, Tiruchirapalli are gratefully acknowledged. Finally. the receipt of suggestions, comments and error reports for further improvement of the book would be welcomed and duly acknowledged.
About the Author
This book was co-authored by K L P Mishra and N Chandrasekaran. While K L P Mishra had a long career as an academic associated with the Regional Engineering College in Tiruchirappalli, N Chandrasekaran served as a Mathematics Professor and visiting faculty member at other reputed colleges in Tiruchirappalli.