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.Table of contents
- Cover
- Title Page
- Contents
- About the Author
- Dedication
- Foreword
- Preface
-
Chapter 1: Basic Terminology
- Introduction
- 1.1 Basics of String
- 1.2 Basics of Set Theory
- 1.3 Relation on Set
- 1.4 Graph and Tree
- 1.5 Basics of Digital Electronics
- 1.6 Digital Circuit
- 1.7 Basics of Automata Theory and Theory of Computation
- 1.8 History of Automata Theory
- 1.9 Use of Automata
- What We Have Learned So Far
- Solved Problems
- Fill in the Blanks
- Exercise
- Chapter 2: Language and Grammar
-
Chapter 3: Finite Automata
- Introduction
- 3.1 History of the Automata Theory
- 3.2 Use of Automata
- 3.3 Characteristics of Automaton
- 3.4 Finite Automata
- 3.5 Graphical and Tabular Representation FA
- 3.6 Transitional System
- 3.7 DFA and NFA
- 3.8 Conversion of an NFA to a DFA
- 3.9 NFA with ∈(null) Move
- 3.10 Equivalence of DFA and NFA
- 3.11 Dead State
- 3.12 Finite Automata with Output
- 3.13 Conversion of One Machine to Another
- 3.14 Minimization of Finite Automata
- 3.15 Myhill–Nerode Theorem
- 3.16 Two-way Finite Automata
- 3.17 Application of Finite Automata
- 3.18 Limitations of Finite Automata
- What We Have Learned So Far
- Solved Problems
- Multiple Choice Questions
- GATE Questions
- Fill in the Blanks
- Exercise
-
Chapter 4: Finite State Machine
- Introduction
- 4.1 Sequence Detector
- 4.2 Binary Counter
- 4.3 Finite State Machine
- 4.4 State Equivalence and Minimization of Machine
- 4.5 Incompletely Specified Machine, Minimal Machine
- 4.6 Merger Graph
- 4.7 Compatibility Graph and Minimal Machine Construction
- 4.8 Merger Table
- 4.9 Finite Memory and Definite Memory Machine
- 4.10 Information Lossless Machine
- 4.11 Inverse Machine
- 4.12 Minimal Inverse Machine
- What We Have Learned So Far
- Solved Problems
- Multiple Choice Questions
- Fill in the Blanks
- Exercise
-
Chapter 5: Regular Expression
- Introduction
- 5.1 Basics of Regular Expression
- 5.2 Basic Operations on Regular Expression
- 5.3 Identities of Regular Expression
- 5.4 The Arden’s Theorem
- 5.5 Construction of Finite Automata from a Regular Expression
- 5.6 NFA with ∈ Move and Conversion to DFA by ∈ -Closure Method
- 5.7 Equivalence of Two Finite Automata
- 5.8 Equivalence of Two Regular Expressions
- 5.9 Construction of Regular Grammar from an RE
- 5.10 Constructing FA from Regular Grammar
- 5.11 Pumping Lemma for Regular Expression
- 5.12 Closure Properties of Regular Set
- 5.13 Decision Problems of Regular Expression
- 5.14 ‘Grep’ and Regular Expression
- 5.15 Application of Regular Expression
- What We Have Learned So Far
- Solved Problems
- Multiple Choice Questions
- GATE Questions
- Fill in the Blanks
- Exercise
-
Chapter 6: Context-free Grammar
- Introduction
- 6.1 Definition of Context-free Grammar
- 6.2 Derivation and Parse Tree
- 6.3 Ambiguity in Context-free Grammar
- 6.4 Left Recursion and Left Factoring
- 6.5 Simplification of Context-free Grammar
- 6.6 Linear Grammar
- 6.7 Normal Form
- 6.8 Closure Properties of Context-free Language
- 6.9 Pumping Lemma for CFL
- 6.10 Ogden’s Lemma for CFL
- 6.11 Decision Problems Related to CFG
- 6.12 CFG and Regular Language
- 6.13 Applications of Context-free Grammar
- What We Have Learned So Far
- Solved Problems
- Multiple Choice Questions
- GATE Questions
- Fill in the Blanks
- Exercise
-
Chapter 7: Pushdown Automata
- Introduction
- 7.1 Basics of PDA
- 7.2 Acceptance by a PDA
- 7.3 DPDA and NPDA
- 7.4 Construction of PDA from CFG
- 7.5 Construction of CFG Equivalent to PDA
- 7.6 Graphical Notation for PDA
- 7.7 Two-stack PDA
- What We Have Learned So Far
- Solved Problems
- Multiple Choice Questions
- GATE Questions
- Fill in the Blanks
- Exercise
-
Chapter 8: Turing Machine
- Introduction
- 8.1 Basics of Turing Machine
- 8.2 Transitional Representation of Turing Machine
- 8.3 Non-deterministic Turing Machine
- 8.4 Conversion of Regular Expression to Turing Machine
- 8.5 Two-stack PDA and Turing Machine
- What We Have Learned So Far
- Solved Problems
- Multiple Choice Questions
- GATE Questions
- Fill in the Blanks
- Exercise
- Chapter 9: Variations of the Turing Machine
-
Chapter 10: Computability and Undecidability
- Introduction
- 10.1 TM Languages
- 10.2 Unrestricted Grammar
- 10.3 Modified Chomsky Hierarchy
- 10.4 Properties of Recursive and Recursively Enumerable Language
- 10.5 Undecidability
- 10.6 Reducibility
- 10.7 Post’s Correspondence Problem (PCP)
- 10.8 Modified Post Correspondence Problem
- What We Have Learned So Far
- Solved Problems
- Multiple Choice Questions
- GATE Questions
- Exercise
-
Chapter 11: Recursive Function
- Introduction
- 11.1 Function
- 11.2 Initial Functions
- 11.3 Recursive Function
- 11.4 Gödel Number
- 11.4.1 Russell’s Paradox
- 11.5 Ackermann’s Function
- 11.6 Minimalization
- 11.7 μ Recursive
- 11.8 λ Calculus
- 11.9 Cantor Diagonal Method
- 11.10 The Rice Theorem
- What We Have Learned So Far
- Solved Problems
- Multiple Choice Questions
- Exercise
-
Chapter 12: Computational Complexity
- Introduction
- 12.1 Types of Computational Complexity
- 12.2 Different Notations for Time Complexity
- 12.3 Problems and Its Classification
- 12.4 Different Types of Time Complexity
- 12.5 The Classes P
- 12.6 Non-polynomial Time Complexity
- 12.7 Polynomial Time Reducibility
- 12.8 Deterministic and Non-deterministic Algorithm
- 12.9 P = NP?—The Million Dollar Question
- 12.10 SAT and CSAT Problem
- 12.11 NP Complete
- 12.12 NP Hard
- 12.13 Space Complexity
- What We Have Learned So Far
- Solved Problems
- Multiple Choice Questions
- GATE Questions
- Exercise
- Chapter 13: Basics of Compiler Design
- Chapter 14: Advance Topics Related to Automata
- References
- Acknowledgements
- Copyright
- Back Cover
Product information
- Title: Introduction to Automata Theory, Formal Languages and Computation
- Author(s):
- Release date: January 2013
- Publisher(s): Pearson India
- ISBN: 9789332516335
You might also like
book
Introduction to Formal Languages, Automata Theory and Computation
Introduction to Formal Languages, Automata Theory and Computation presents the theoretical concepts in a concise and …
book
Formal Languages and Automata Theory
Formal Languages and Automata Theory deals with the mathematical abstraction model of computation and its relation …
book
Express Learning: Automata Theory and Formal Languages
Express Learning is a series of books designed as quick reference guides to important undergraduate computer …
book
An Introduction to Formal Languages and Automata, 6th Edition
The Sixth Edition of An Introduction to Formal Languages and Automata provides an accessible, student-friendly presentation …