Introduction to Automata Theory, Formal Languages and Computation.
Kandar, Shyamalendu.
Introduction to Automata Theory, Formal Languages and Computation. - 1st ed. - 1 online resource (656 pages)
Cover -- Contents -- Foreword -- Preface -- Acknowledgements -- About the Author -- Chapter 1 : Basic Terminology -- Introduction -- 1.1 Basics of String -- 1.2 Basics of Set Theory -- 1.2.1 Subset -- 1.2.2 Finite and Infinite Set -- 1.2.3 Equal -- 1.2.4 Algebraic Operations on Sets -- 1.2.5 Properties Related to Basic Operation -- 1.3 Relation on Set -- 1.4 Graph and Tree -- 1.4.1 Graph -- 1.4.2 Incident and Degree of a Vertex -- 1.4.3 Isolated Vertex, Pendant Vertex -- 1.4.4 Walk -- 1.4.5 Path and Circuit -- 1.4.6 Connected and Disconnected Graph -- 1.4.7 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 -- Introduction -- 2.1 Grammar -- 2.2 The Chomsky Hierarchy -- What We Have Learned So Far -- Solved Problems -- Multiple Choice Questions -- GATE Questions -- Fill in the Blanks -- Exercise -- Chapter 3 : Finite Automata -- Introduction -- 3.1 History of the Automata Theory -- 3.2 Use of Automata -- 3.3 Characteristics of Automaton -- 3.3.1 Characteristics -- 3.4 Finite Automata -- 3.5 Graphical and Tabular Representation of FA -- 3.6 Transitional System -- 3.6.1 Acceptance of a String by Finite Automata -- 3.7 DFA and NFA -- 3.8 Conversion of an NFA to a DFA -- 3.8.1 Process of Converting an NFA to a DFA -- 3.9 NFA with e (null) Move -- 3.9.1 Usefulness of NFA with E Move -- 3.9.2 Conversion of an NFA with e Moves to DFA without e Move -- 3.10 Equivalence of DFA and NFA -- 3.11 Dead State -- 3.12 Finite Automata with Output -- 3.12.1 The Mealy Machine -- 3.12.2 The Moore Machine -- 3.12.3 Tabular and Transitional Representation of the Mealy and Moore Machines -- 3.12.3.1 Tabular. 3.12.3.2 Transitional -- 3.13 Conversion of One Machine to Another -- 3.13.1 Tabular Format -- 3.13.2 Transitional Format -- 3.14 Minimization of Finite Automata -- 3.14.1 Process of Minimizing -- 3.15 Myhill-Nerode Theorem -- 3.15.1 Equivalence Relation -- 3.15.2 Statement of the Myhill-Nerode Theorem -- 3.15.3 Myhill-Nerode Theorem in Minimizing a DFA -- 3.16 Two-way Finite Automata -- 3.17 Applications 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.2.1 Designing Using Flip Flop (T Flip Flop and SR Flip Flop) -- 4.3 Finite State Machine -- 4.3.1 Capabilities and Limitations of Finite-State Machine -- 4.4 State Equivalence and Minimization of Machine -- 4.5 Incompletely Specified Machine, Minimal Machine -- 4.5.1 Simplification -- 4.6 Merger Graph -- 4.7 Compatibility Graph and Minimal Machine Construction -- 4.7.1 Compatible Pair -- 4.7.2 Implied Pair -- 4.7.3 Compatibility Graph -- 4.7.4 Minimal Machine Construction -- 4.7.5 Minimal Machine -- 4.8 Merger Table -- 4.8.1 Construction of a Merger Table -- 4.9 Finite Memory and Definite Memory Machine -- 4.9.1 Finite Memory Machine -- 4.9.2 Constructing the Method of Connection Matrix -- 4.9.3 Vanishing of Connection Matrix -- 4.9.4 Definite Memory Machine -- 4.10 Information Lossless Machine -- 4.10.1 Test for Information Losslessness -- 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.1.1 Some Formal Recursive Definitions of RE. 5.2 Basic Operations on Regular Expression -- 5.2.1 Kleene's Closure -- 5.3 Identities of Regular Expression -- 5.4 The Arden's Theorem -- 5.4.1 Process of Constructing Regular Expression from Finite Automata -- 5.5 Construction of Finite Automata from a Regular Expression -- 5.5.1 Conversion of an RE to NFA with e transition -- 5.5.2 Direct Conversion of RE to DFA -- 5.6 NFA with e Move and Conversion to DFA by e-Closure Method -- 5.6.1 Conversion of an NFA with e move to a DFA -- 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 Applications 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.1.1 Backus Naur Form (BNF) -- 6.2 Derivation and Parse Tree -- 6.2.1 Derivation -- 6.2.2 Parse Tree -- 6.3 Ambiguity in Context-free Grammar -- 6.4 Left Recursion and Left Factoring -- 6.4.1 Left Recursion -- 6.4.2 Left Factoring -- 6.5 Simplification of Context-free Grammar -- 6.5.1 Removal of Useless Symbols -- 6.5.2 Removal of Unit Productions -- 6.5.3 Removal of Null Productions -- 6.6 Linear Grammar -- 6.6.1 Right Linear to Left Linear -- 6.6.2 Left Linear to Right Linear -- 6.7 Normal Form -- 6.7.1 Chomsky Normal Form -- 6.7.2 Greibach Normal Form -- 6.8 Closure Properties of Context-free Language -- 6.8.1 Closed Under Union -- 6.8.2 Closed Under Concatenation -- 6.8.3 Closed Under Star Closure -- 6.8.4 Closed Under Intersection. 6.8.5 Not Closed Under Complementation -- 6.8.6 Every Regular Language is a Context-free Language -- 6.9 Pumping Lemma for CFL -- 6.10 Ogden's Lemma for CFL -- 6.11 Decision Problems Related to CFG -- 6.11.1 Emptiness -- 6.11.2 Finiteness -- 6.11.3 Membership Problem -- 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.1.1 Definition -- 7.1.2 Mechanical Diagram of the PDA -- 7.2 Acceptance by a PDA -- 7.2.1 Accepted by an Empty Stack (Store) -- 7.2.2 Accepted by the Final State -- 7.3 DPDA and NPDA -- 7.3.1 Deterministic Pushdown Automata (DPDA) -- 7.3.2 Non-deterministic Pushdown Automata (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.1.1 Mechanical Diagram -- 8.1.2 Instantaneous Description (ID) in Respect of TM -- 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 -- 8.5.1 Minsky Theorem -- 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 -- Introduction -- 9.1 Variations of the Turing Machine -- 9.1.1 Multi-tape Turing Machine -- 9.1.2 Multi-head Turing Machine -- 9.1.3 Two-way Infinite Tape -- 9.1.4 K-dimensional Turing Machine. 9.1.5 Non-deterministic Turing Machine -- 9.1.6 Enumerator -- 9.2 Turing Machine as an Integer Function -- 9.3 Universal Turing Machine -- 9.4 Linear-Bounded Automata (LBA) -- 9.5 Post Machine -- 9.6 Church's Thesis -- What We Have Learned So Far -- Solved Problems -- Multiple Choice Questions -- GATE Questions -- Exercise -- Chapter 10 : Computability and Undecidability -- Introduction -- 10.1 TM Languages -- 10.1.1 Turing Acceptable -- 10.1.2 Turing Decidable -- 10.2 Unrestricted Grammar -- 10.2.1 Turing Machine to Unrestricted Grammar -- 10.2.2 Kuroda Normal Form -- 10.2.3 Conversion of a Grammar into the Kuroda Normal Form -- 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 -- 10.8.1 Reduction of MPCP to PCP -- What We Have Learned So Far -- Solved Problems -- Multiple Choice Questions -- GATE Questions -- Exercise -- Chapter 11 : Recursive Function -- Introduction -- 11.1 Function -- 11.1.1 Different Types of Functions -- 11.2 Initial Functions -- 11.3 Recursive Function -- 11.4 G�odel Number -- 11.4.1 Russell's Paradox -- 11.5 Ackermann's Function -- 11.6 Minimalization -- 11.7 µ Recursive -- 11.7.1 Properties of a (So(B Recursive Function -- 11.8 l 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.1.1 Time Complexity -- 12.1.2 Space Complexity -- 12.2 Different Notations for Time Complexity -- 12.2.1 Big Oh Notation -- 12.2.2 Big Omega (W) Notation -- 12.2.3 Theta Notation (Q) -- 12.2.4 Little-oh Notation (o) -- 12.2.5 Little Omega Notation (w). 12.3 Problems and Its Classification.
Formal languages and automata theory is the study of abstract machines and how these can be used for solving problems. The book has a simplistic approach to topics like automata theory, formal languages and theory of computation and explains them exhaustively. The difficult topics are described in a step-wise manner, which makes it easy for the students to comprehend them. 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.
9789332516328
Electronic books.
005.131
Introduction to Automata Theory, Formal Languages and Computation. - 1st ed. - 1 online resource (656 pages)
Cover -- Contents -- Foreword -- Preface -- Acknowledgements -- About the Author -- Chapter 1 : Basic Terminology -- Introduction -- 1.1 Basics of String -- 1.2 Basics of Set Theory -- 1.2.1 Subset -- 1.2.2 Finite and Infinite Set -- 1.2.3 Equal -- 1.2.4 Algebraic Operations on Sets -- 1.2.5 Properties Related to Basic Operation -- 1.3 Relation on Set -- 1.4 Graph and Tree -- 1.4.1 Graph -- 1.4.2 Incident and Degree of a Vertex -- 1.4.3 Isolated Vertex, Pendant Vertex -- 1.4.4 Walk -- 1.4.5 Path and Circuit -- 1.4.6 Connected and Disconnected Graph -- 1.4.7 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 -- Introduction -- 2.1 Grammar -- 2.2 The Chomsky Hierarchy -- What We Have Learned So Far -- Solved Problems -- Multiple Choice Questions -- GATE Questions -- Fill in the Blanks -- Exercise -- Chapter 3 : Finite Automata -- Introduction -- 3.1 History of the Automata Theory -- 3.2 Use of Automata -- 3.3 Characteristics of Automaton -- 3.3.1 Characteristics -- 3.4 Finite Automata -- 3.5 Graphical and Tabular Representation of FA -- 3.6 Transitional System -- 3.6.1 Acceptance of a String by Finite Automata -- 3.7 DFA and NFA -- 3.8 Conversion of an NFA to a DFA -- 3.8.1 Process of Converting an NFA to a DFA -- 3.9 NFA with e (null) Move -- 3.9.1 Usefulness of NFA with E Move -- 3.9.2 Conversion of an NFA with e Moves to DFA without e Move -- 3.10 Equivalence of DFA and NFA -- 3.11 Dead State -- 3.12 Finite Automata with Output -- 3.12.1 The Mealy Machine -- 3.12.2 The Moore Machine -- 3.12.3 Tabular and Transitional Representation of the Mealy and Moore Machines -- 3.12.3.1 Tabular. 3.12.3.2 Transitional -- 3.13 Conversion of One Machine to Another -- 3.13.1 Tabular Format -- 3.13.2 Transitional Format -- 3.14 Minimization of Finite Automata -- 3.14.1 Process of Minimizing -- 3.15 Myhill-Nerode Theorem -- 3.15.1 Equivalence Relation -- 3.15.2 Statement of the Myhill-Nerode Theorem -- 3.15.3 Myhill-Nerode Theorem in Minimizing a DFA -- 3.16 Two-way Finite Automata -- 3.17 Applications 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.2.1 Designing Using Flip Flop (T Flip Flop and SR Flip Flop) -- 4.3 Finite State Machine -- 4.3.1 Capabilities and Limitations of Finite-State Machine -- 4.4 State Equivalence and Minimization of Machine -- 4.5 Incompletely Specified Machine, Minimal Machine -- 4.5.1 Simplification -- 4.6 Merger Graph -- 4.7 Compatibility Graph and Minimal Machine Construction -- 4.7.1 Compatible Pair -- 4.7.2 Implied Pair -- 4.7.3 Compatibility Graph -- 4.7.4 Minimal Machine Construction -- 4.7.5 Minimal Machine -- 4.8 Merger Table -- 4.8.1 Construction of a Merger Table -- 4.9 Finite Memory and Definite Memory Machine -- 4.9.1 Finite Memory Machine -- 4.9.2 Constructing the Method of Connection Matrix -- 4.9.3 Vanishing of Connection Matrix -- 4.9.4 Definite Memory Machine -- 4.10 Information Lossless Machine -- 4.10.1 Test for Information Losslessness -- 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.1.1 Some Formal Recursive Definitions of RE. 5.2 Basic Operations on Regular Expression -- 5.2.1 Kleene's Closure -- 5.3 Identities of Regular Expression -- 5.4 The Arden's Theorem -- 5.4.1 Process of Constructing Regular Expression from Finite Automata -- 5.5 Construction of Finite Automata from a Regular Expression -- 5.5.1 Conversion of an RE to NFA with e transition -- 5.5.2 Direct Conversion of RE to DFA -- 5.6 NFA with e Move and Conversion to DFA by e-Closure Method -- 5.6.1 Conversion of an NFA with e move to a DFA -- 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 Applications 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.1.1 Backus Naur Form (BNF) -- 6.2 Derivation and Parse Tree -- 6.2.1 Derivation -- 6.2.2 Parse Tree -- 6.3 Ambiguity in Context-free Grammar -- 6.4 Left Recursion and Left Factoring -- 6.4.1 Left Recursion -- 6.4.2 Left Factoring -- 6.5 Simplification of Context-free Grammar -- 6.5.1 Removal of Useless Symbols -- 6.5.2 Removal of Unit Productions -- 6.5.3 Removal of Null Productions -- 6.6 Linear Grammar -- 6.6.1 Right Linear to Left Linear -- 6.6.2 Left Linear to Right Linear -- 6.7 Normal Form -- 6.7.1 Chomsky Normal Form -- 6.7.2 Greibach Normal Form -- 6.8 Closure Properties of Context-free Language -- 6.8.1 Closed Under Union -- 6.8.2 Closed Under Concatenation -- 6.8.3 Closed Under Star Closure -- 6.8.4 Closed Under Intersection. 6.8.5 Not Closed Under Complementation -- 6.8.6 Every Regular Language is a Context-free Language -- 6.9 Pumping Lemma for CFL -- 6.10 Ogden's Lemma for CFL -- 6.11 Decision Problems Related to CFG -- 6.11.1 Emptiness -- 6.11.2 Finiteness -- 6.11.3 Membership Problem -- 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.1.1 Definition -- 7.1.2 Mechanical Diagram of the PDA -- 7.2 Acceptance by a PDA -- 7.2.1 Accepted by an Empty Stack (Store) -- 7.2.2 Accepted by the Final State -- 7.3 DPDA and NPDA -- 7.3.1 Deterministic Pushdown Automata (DPDA) -- 7.3.2 Non-deterministic Pushdown Automata (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.1.1 Mechanical Diagram -- 8.1.2 Instantaneous Description (ID) in Respect of TM -- 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 -- 8.5.1 Minsky Theorem -- 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 -- Introduction -- 9.1 Variations of the Turing Machine -- 9.1.1 Multi-tape Turing Machine -- 9.1.2 Multi-head Turing Machine -- 9.1.3 Two-way Infinite Tape -- 9.1.4 K-dimensional Turing Machine. 9.1.5 Non-deterministic Turing Machine -- 9.1.6 Enumerator -- 9.2 Turing Machine as an Integer Function -- 9.3 Universal Turing Machine -- 9.4 Linear-Bounded Automata (LBA) -- 9.5 Post Machine -- 9.6 Church's Thesis -- What We Have Learned So Far -- Solved Problems -- Multiple Choice Questions -- GATE Questions -- Exercise -- Chapter 10 : Computability and Undecidability -- Introduction -- 10.1 TM Languages -- 10.1.1 Turing Acceptable -- 10.1.2 Turing Decidable -- 10.2 Unrestricted Grammar -- 10.2.1 Turing Machine to Unrestricted Grammar -- 10.2.2 Kuroda Normal Form -- 10.2.3 Conversion of a Grammar into the Kuroda Normal Form -- 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 -- 10.8.1 Reduction of MPCP to PCP -- What We Have Learned So Far -- Solved Problems -- Multiple Choice Questions -- GATE Questions -- Exercise -- Chapter 11 : Recursive Function -- Introduction -- 11.1 Function -- 11.1.1 Different Types of Functions -- 11.2 Initial Functions -- 11.3 Recursive Function -- 11.4 G�odel Number -- 11.4.1 Russell's Paradox -- 11.5 Ackermann's Function -- 11.6 Minimalization -- 11.7 µ Recursive -- 11.7.1 Properties of a (So(B Recursive Function -- 11.8 l 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.1.1 Time Complexity -- 12.1.2 Space Complexity -- 12.2 Different Notations for Time Complexity -- 12.2.1 Big Oh Notation -- 12.2.2 Big Omega (W) Notation -- 12.2.3 Theta Notation (Q) -- 12.2.4 Little-oh Notation (o) -- 12.2.5 Little Omega Notation (w). 12.3 Problems and Its Classification.
Formal languages and automata theory is the study of abstract machines and how these can be used for solving problems. The book has a simplistic approach to topics like automata theory, formal languages and theory of computation and explains them exhaustively. The difficult topics are described in a step-wise manner, which makes it easy for the students to comprehend them. 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.
9789332516328
Electronic books.
005.131