| 000 | 11264nam a22003973i 4500 | ||
|---|---|---|---|
| 999 |
_c25597 _d25597 |
||
| 001 | EBC5125104 | ||
| 003 | MiAaPQ | ||
| 005 | 20190105120855.0 | ||
| 006 | m o d | | ||
| 007 | cr cnu|||||||| | ||
| 008 | 181231s2013 xx o ||||0 eng d | ||
| 020 |
_a9789332516328 _q(electronic bk.) |
||
| 035 | _a(MiAaPQ)EBC5125104 | ||
| 035 | _a(Au-PeEL)EBL5125104 | ||
| 035 | _a(CaONFJC)MIL514415 | ||
| 035 | _a(OCoLC)900316601 | ||
| 040 |
_aMiAaPQ _beng _erda _epn _cMiAaPQ _dMiAaPQ |
||
| 082 |
_223 _a005.131 |
||
| 100 | 1 | _aKandar, Shyamalendu. | |
| 245 | 1 | 0 | _aIntroduction to Automata Theory, Formal Languages and Computation. |
| 250 | _a1st ed. | ||
| 300 | _a1 online resource (656 pages) | ||
| 505 | 0 | _aCover -- 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. | |
| 505 | 8 | _a3.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. | |
| 505 | 8 | _a5.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. | |
| 505 | 8 | _a6.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. | |
| 505 | 8 | _a9.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). | |
| 505 | 8 | _a12.3 Problems and Its Classification. | |
| 520 | _aFormal 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. | ||
| 590 | _aElectronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2018. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries. | ||
| 655 | 4 | _aElectronic books. | |
| 776 | 0 | 8 |
_iPrint version: _aKandar, Shyamalendu _tIntroduction to Automata Theory, Formal Languages and Computation _dNoida : Pearson India,c2013 |
| 797 | 2 | _aProQuest (Firm) | |
| 856 | 4 | 0 |
_uhttps://ebookcentral.proquest.com/lib/cethalassery/detail.action?docID=5125104 _zClick to View |
| 942 |
_2ddc _cBK |
||