## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## Book Description

Formal languages and automata theory is the study of abstract machines and how these can be used for solving problems. The book has a simple and exhaustive approach to topics like automata theory, formal languages and theory of computation. These descriptions are followed by numerous relevant examples related to the topic. A brief introductory chapter on compilers explaining its relation to theory of computation is also given.

1. Cover
2. Title Page
3. Contents
5. Dedication
6. Foreword
7. Preface
8. Chapter 1: Basic Terminology
1. Introduction
2. 1.1 Basics of String
3. 1.2 Basics of Set Theory
4. 1.3 Relation on Set
5. 1.4 Graph and Tree
6. 1.5 Basics of Digital Electronics
7. 1.6 Digital Circuit
8. 1.7 Basics of Automata Theory and Theory of Computation
9. 1.8 History of Automata Theory
10. 1.9 Use of Automata
11. What We Have Learned So Far
12. Solved Problems
13. Fill in the Blanks
14. Exercise
9. Chapter 2: Language and Grammar
10. Chapter 3: Finite Automata
1. Introduction
2. 3.1 History of the Automata Theory
3. 3.2 Use of Automata
4. 3.3 Characteristics of Automaton
5. 3.4 Finite Automata
6. 3.5 Graphical and Tabular Representation FA
7. 3.6 Transitional System
8. 3.7 DFA and NFA
9. 3.8 Conversion of an NFA to a DFA
10. 3.9 NFA with ∈(null) Move
11. 3.10 Equivalence of DFA and NFA
13. 3.12 Finite Automata with Output
14. 3.13 Conversion of One Machine to Another
15. 3.14 Minimization of Finite Automata
16. 3.15 Myhill–Nerode Theorem
17. 3.16 Two-way Finite Automata
18. 3.17 Application of Finite Automata
19. 3.18 Limitations of Finite Automata
20. What We Have Learned So Far
21. Solved Problems
22. Multiple Choice Questions
23. GATE Questions
24. Fill in the Blanks
25. Exercise
11. Chapter 4: Finite State Machine
1. Introduction
2. 4.1 Sequence Detector
3. 4.2 Binary Counter
4. 4.3 Finite State Machine
5. 4.4 State Equivalence and Minimization of Machine
6. 4.5 Incompletely Specified Machine, Minimal Machine
7. 4.6 Merger Graph
8. 4.7 Compatibility Graph and Minimal Machine Construction
9. 4.8 Merger Table
10. 4.9 Finite Memory and Definite Memory Machine
11. 4.10 Information Lossless Machine
12. 4.11 Inverse Machine
13. 4.12 Minimal Inverse Machine
14. What We Have Learned So Far
15. Solved Problems
16. Multiple Choice Questions
17. Fill in the Blanks
18. Exercise
12. Chapter 5: Regular Expression
1. Introduction
2. 5.1 Basics of Regular Expression
3. 5.2 Basic Operations on Regular Expression
4. 5.3 Identities of Regular Expression
5. 5.4 The Arden’s Theorem
6. 5.5 Construction of Finite Automata from a Regular Expression
7. 5.6 NFA with ∈ Move and Conversion to DFA by ∈ -Closure Method
8. 5.7 Equivalence of Two Finite Automata
9. 5.8 Equivalence of Two Regular Expressions
10. 5.9 Construction of Regular Grammar from an RE
11. 5.10 Constructing FA from Regular Grammar
12. 5.11 Pumping Lemma for Regular Expression
13. 5.12 Closure Properties of Regular Set
14. 5.13 Decision Problems of Regular Expression
15. 5.14 ‘Grep’ and Regular Expression
16. 5.15 Application of Regular Expression
17. What We Have Learned So Far
18. Solved Problems
19. Multiple Choice Questions
20. GATE Questions
21. Fill in the Blanks
22. Exercise
13. Chapter 6: Context-free Grammar
1. Introduction
2. 6.1 Definition of Context-free Grammar
3. 6.2 Derivation and Parse Tree
4. 6.3 Ambiguity in Context-free Grammar
5. 6.4 Left Recursion and Left Factoring
6. 6.5 Simplification of Context-free Grammar
7. 6.6 Linear Grammar
8. 6.7 Normal Form
9. 6.8 Closure Properties of Context-free Language
10. 6.9 Pumping Lemma for CFL
11. 6.10 Ogden’s Lemma for CFL
12. 6.11 Decision Problems Related to CFG
13. 6.12 CFG and Regular Language
14. 6.13 Applications of Context-free Grammar
15. What We Have Learned So Far
16. Solved Problems
17. Multiple Choice Questions
18. GATE Questions
19. Fill in the Blanks
20. Exercise
14. Chapter 7: Pushdown Automata
1. Introduction
2. 7.1 Basics of PDA
3. 7.2 Acceptance by a PDA
4. 7.3 DPDA and NPDA
5. 7.4 Construction of PDA from CFG
6. 7.5 Construction of CFG Equivalent to PDA
7. 7.6 Graphical Notation for PDA
8. 7.7 Two-stack PDA
9. What We Have Learned So Far
10. Solved Problems
11. Multiple Choice Questions
12. GATE Questions
13. Fill in the Blanks
14. Exercise
15. Chapter 8: Turing Machine
1. Introduction
2. 8.1 Basics of Turing Machine
3. 8.2 Transitional Representation of Turing Machine
4. 8.3 Non-deterministic Turing Machine
5. 8.4 Conversion of Regular Expression to Turing Machine
6. 8.5 Two-stack PDA and Turing Machine
7. What We Have Learned So Far
8. Solved Problems
9. Multiple Choice Questions
10. GATE Questions
11. Fill in the Blanks
12. Exercise
16. Chapter 9: Variations of the Turing Machine
1. Introduction
2. 9.1 Variations of the Turing Machine
3. 9.2 Turing Machine as an Integer Function
4. 9.3 Universal Turing Machine
5. 9.4 Linear-Bounded Automata (LBA)
6. 9.5 Post Machine
7. 9.6 Church’s Thesis
8. What We Have Learned So Far
9. Solved Problems
10. Multiple Choice Questions
11. GATE Questions
12. Exercise
17. Chapter 10: Computability and Undecidability
1. Introduction
2. 10.1 TM Languages
3. 10.2 Unrestricted Grammar
4. 10.3 Modified Chomsky Hierarchy
5. 10.4 Properties of Recursive and Recursively Enumerable Language
6. 10.5 Undecidability
7. 10.6 Reducibility
8. 10.7 Post’s Correspondence Problem (PCP)
9. 10.8 Modified Post Correspondence Problem
10. What We Have Learned So Far
11. Solved Problems
12. Multiple Choice Questions
13. GATE Questions
14. Exercise
18. Chapter 11: Recursive Function
1. Introduction
2. 11.1 Function
3. 11.2 Initial Functions
4. 11.3 Recursive Function
5. 11.4 Gödel Number
7. 11.5 Ackermann’s Function
8. 11.6 Minimalization
9. 11.7 μ Recursive
10. 11.8 λ Calculus
11. 11.9 Cantor Diagonal Method
12. 11.10 The Rice Theorem
13. What We Have Learned So Far
14. Solved Problems
15. Multiple Choice Questions
16. Exercise
19. Chapter 12: Computational Complexity
1. Introduction
2. 12.1 Types of Computational Complexity
3. 12.2 Different Notations for Time Complexity
4. 12.3 Problems and Its Classification
5. 12.4 Different Types of Time Complexity
6. 12.5 The Classes P
7. 12.6 Non-polynomial Time Complexity
8. 12.7 Polynomial Time Reducibility
9. 12.8 Deterministic and Non-deterministic Algorithm
10. 12.9 P = NP?—The Million Dollar Question
11. 12.10 SAT and CSAT Problem
12. 12.11 NP Complete
13. 12.12 NP Hard
14. 12.13 Space Complexity
15. What We Have Learned So Far
16. Solved Problems
17. Multiple Choice Questions
18. GATE Questions
19. Exercise
20. Chapter 13: Basics of Compiler Design
1. Introduction
2. 13.1 Definition
3. 13.2 Types of Compiler
4. 13.3 Major Parts of Compiler
5. What We Have Learned So Far
6. Multiple Choice Questions
7. GATE Questions
8. Exercise
21. Chapter 14: Advance Topics Related to Automata
1. Introduction
2. 14.1 Matrix Grammar
3. 14.2 Probabilistic Finite Automata
4. 14.3 Cellular Automata
22. References
23. Acknowledgements