The book introduces readers to Theory of Computation, one of the fundamental pillars of Computer Science, and can be used as a core textbook by undergraduate students of Engineering. It offers a cohesive presentation of all aspects of Theoretical Computer Science, namely, automata, formal languages, computability and complexity. It also covers the mathematical preliminaries necessary for the subject.
As Theory of Computation forms an important part of the syllabus of various national and state-level competitive examinations and is also a high-scoring area, several problems from previous competitive examinations have also been included in this book, and shortcut tricks have been provided, where feasible.
Salient features
Bikash Kanti Sarkar is a faculty member of the Department of Computer Science and Engineering, BIT, Mesra, Ranchi. A PhD in Computer Science from Jadavpur University, he obtained his MCA from BESU (Howrah), MPhil (Computer Science) from Annamalai University and MSc (Mathematics) from IIT Kharagpur. He has more than 20 years of experience as a teacher, and has authored several books and research papers in international journals of repute.
Ambuj Kumar holds an MTech in Computer Science from IIT Delhi and a BE in Computer Science from BIT, Mesra, Ranchi. He is a seasoned software professional with 13 years of experience in leading software companies, including an 8-year stint at Microsoft (Hyderabad).
Preface Acknowledgements Chapter 1 Basic Mathematics for Theory of Computation 1.1 Introduction 1.2 Mathematical Tools for Modelling Automata 1.2.1 Set 1.2.2 Logic 1.2.3 Graph 1.2.4 Relation 1.2.5 Function 1.2.6 Language 1.2.7 Pigeonhole Principle 1.2.8 Mathematical Induction 1.3 Mathematical Concepts for Complexity Analysis 1.3.1 Function 1.3.2 Asymptotic Notation 1.4 Additional Solved Problems Exercises Chapter 2 Finite Automata 2.1 Introduction 2.2 Basic Characteristics of Automata 2.3 Basic Categories of Automata 2.4 Finite State Machine and its Types 2.4.1 Informal Picture 2.4.2 High-level Description 2.4.3 Deterministic Finite Automaton (DFA) 2.4.4 Non-deterministic Finite Automaton (NDFA or NFA) 2.5 Graphical Shapes Used to Draw Finite Automata 2.6 Designing Some Basic Finite Automata 2.7 Basic Operations on DFA 2.7.1 Finding the Complement of a Given DFA 2.7.2 Product Automata 2.8 Basic Tips for Designing Finite Automata 2.9 NDFA and its Categories 2.9.1 NDFA Without e Move 2.9.2 Epsilon NFA (e NFA) 2.10 Minimisation of Finite Automata 2.10.1 DFA Minimisation Using Equivalence Theorem 2.10.2 Myhill–Nerode Theorem/Table-filling DFA Minimisation Algorithm 2.11 Finite State Machine with Output 2.11.1 Moore Machine 2.11.2 Mealy Machine 2.11.3 Transformation of Moore Machine to Mealy Machine 2.11.4 Transformation of Mealy Machine to Moore Machine 2.11.5 FA-based String Matching Algorithm 2.12 Additional Solved Problems 2.13 Research Directions Exercises Chapter 3 Regular Expressions 3.1 Introduction 3.2 Regular Expressions and Basic Operations 3.3 Examples of Regular Expressions 3.4 Algebraic Laws of Regular Expressions 3.5 Finite and Infinite Languages 3.6 Equivalence of Finite Automaton and Regular Expression 3.6.1 Designing Equivalent DFA for Regular Expressions 3.6.2 Deriving Equivalent Regular Expressions from DFA 3.7 Additional Tips for Problems on FA and RE 3.8 Pumping Lemma for Regular Languages 3.9 Closure Properties of Regular Languages 3.10 Non-Regular Languages 3.11 Applications of Finite Automata and Regular Expressions 3.12 Additional Solved Problems 3.13 Research Directions Exercises Chapter 4 Grammar 4.1 Introduction 4.2 Formal Definition 4.3 Chomsky Hierarchy of Grammars 4.4 Strategies to Simplify Context-Free Grammars 4.5 Conversion of Finite Automata to Regular Grammar and Regular Expression to Regular Grammar 4.5.1 Designing Right-Linear Regular Grammar (RLRG) from DFA 4.5.2 Designing Left-Linear Regular Grammar (LLRG) from DFA 4.6 Derivation/Parse Tree 4.6.1 Parsing Techniques 4.6.2 Ambiguous and Unambiguous Grammar 4.7 Derivation of Normal Forms of Context-Free Grammar 4.8 Pumping Lemma for Context-Free Language 4.9 Applications of Grammars and Formal Languages 4.10 Additional Solved Problems 4.11 Research Directions Exercises Annexure I: Converting a Right-Linear Regular Grammar to NFA Chapter 5 Pushdown Automata 5.1 Introduction 5.2 Formal Definition 5.2.1 Types of Pushdown Automata 5.2.2 Non-deterministic Pushdown Automata (NPDA) 5.3 Closure Properties of Context-Free Languages 5.4 Pushdown Automata and Parsing 5.5 Additional Solved Problems 5.6 Research Directions Exercises Chapter 6 Turing Machine 6.1 Introduction 6.2 Formal Definition of Single-tape Turing Machine 6.2.1 Representation of Turing Machine 6.3 Variations of Turing Machine 6.3.1 Multi-tape and Multi-track TM 6.4 TM as Accepting and Computing Device 6.5 Halting Problem 6.6 Turing Machine and Languages 6.6.1 Types of Languages 6.7 Comparison of FA, PDA, LBA and TM 6.8 Properties of Recursive and Recursively Enumerable Languages 6.9 Church Thesis 6.10 Post-correspondence Problem 6.11 Additional Solved Problems 6.12 Research Directions Exercises Chapter 7 Classes of Problems 7.1 Introduction 7.2 Types of Problems 7.3 Classes of Problems 7.3.1 P Problem 7.3.2 NP Problem 7.3.3 NP-Complete Problem 7.3.4 NP-Hard Problem 7.3.5 Summary of Classes of Problems 7.4 Introduction to Recursion Theory 7.5 Additional Solved Problems 7.6 Research Directions Exercises Appendix: Competitive Examination Questions and Answers Index