**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.