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*

- Proper mathematical explanation for various computational models, numerous figures, highlighted notes and shortcut tips for easy understanding of ideas
- Numerous solved examples mapping with other relevant subjects and real-world problems
- Ideas for research direction and project-based problems at the end of every chapter
- Key Points to draw attention to the important ideas/concepts discussed
- Exercises comprising practice problems as well as MCQs at the end of every chapter
- Competitive examination section with solved examples of several national and state-level competitive examinations, such as GATE, NET, SET and PhD entrance

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