Express Learning: Automata Theory and Formal Languages

Table of contents

1. Cover Page
2. Title Page
3. Copyright Page
4. Dedication Page
5. Contents
6. About the Author
7. Foreword
8. Preface
9. Acknowledgements
10. 1. Finite State Machine
    1. 1.1 Basics of Automata
    2. 1.2 Finite State Machine
    3. 1.3 State Equivalence and Minimization of Machine
    4. 1.4 Incompletely Specified Machine and Minimal Machine
    5. 1.5 Merger Graph and Compatibility Graph
    6. 1.6 Finite Memory and Definite Memory Machine
    7. 1.7 Information Lossless Machine and Inverse Machine
    8. 1.8 Inverse Machine
       1. What We Have Learned so Far
       2. Solved Problems
       3. Multiple Choice Questions
       4. Exercises
       5. Fill in the Blanks
11. 2. Language and Grammar
    1. 2.1 Basic Terminology and Definitions
    2. 2.2 Grammar and Language
    3. 2.3 Chomsky Hierarchy
    4. 2.4 Examples
    5. 2.5 Context-sensitive Grammar
       1. What We Have Learned so Far
       2. Solved Problems
       3. Multiple Choice Questions
       4. Exercises
       5. Fill in the Blanks
12. 3. Finite Automata
    1. 3.1 Basics About Finite Automata
    2. 3.2 Transitional System
    3. 3.3 Deterministic Finite Automata and Non-Deterministic Finite Automata
    4. 3.4 NFA with Null Move
    5. 3.5 Dead State
    6. 3.6 Finite Automata with Output
    7. 3.7 Conversion of Moore To Mealy Machine by Tabular Format
    8. 3.8 Conversion of Mealy to Moore Machine by Tabular Format
    9. 3.9 Conversion of Moore to Mealy Machine by Transitional Format
    10. 3.10 Conversion of Mealy to Moore Machine by Transitional Format
    11. 3.11 Minimization of Finite Automata
    12. 3.12 Myhill-Nerode Theorem
        1. What We Have Learned so Far
        2. Solved Problems
        3. Multiple Choice Questions
        4. Exercises
        5. Fill in the Blanks
13. 4. Regular Expression
    1. 4.1 Basics of Regular Expression
    2. 4.2 Arden Theorem
    3. 4.3 Construction of Finite Automata Equivalent to a Regular Expression
    4. 4.4 NFA With £ Move and Conversion to DFA by £ - Closure Method
    5. 4.5 Equivalence of Two Finite Automata and Two Regular Expressions
    6. 4.6 Construction of Regular Grammar from a Regular Expression
    7. 4.7 Pumping Lemma and its Application
    8. 4.8 Closure Properties of Regular Set
       1. What We Have Learned so Far
       2. Solved Problems
       3. Multiple Choice Questions
       4. Exercises
       5. Fill in the Blanks
14. 5. Context Free Grammar
    1. 5.1 Context Free Grammar: Definition and Examples
    2. 5.2 Derivation and Parse Tree
    3. 5.3 Ambiguity
    4. 5.4 Left Recursion and Left Factoring
    5. 5.5 Simplification of CFG
    6. 5.6 Normal Form
    7. 5.7 Constructing FA from Regular Grammar
    8. 5.8 Closure Properties of CFL
    9. 5.9 Pumping Lemma for CFL
    10. 5.10 Ogden's Lemma for CFL
    11. 5.11 Decision Algorithms
        1. What We Have Learned so Far
        2. Solved Problems
        3. Multiple Choice Questions
        4. Exercises
        5. Fill in the Blanks
15. 6. Pushdown Automata
    1. 6.1 Basics of Pushdown Automata
    2. 6.2 Acceptance by a PDA
    3. 6.3 Examples
    4. 6.4 Deterministic PDA and Non-Deterministic PDA
    5. 6.5 Pushdown Automata from Context Free Grammar
    6. 6.6 Graphical Notation for PDA
       1. What We Have Learned so Far
       2. Solved Problems
       3. Multiple Choice Questions
       4. Exercises
       5. Fill in the Blanks
16. 7. Turing Machine
    1. 7.1 Basic of Turing Machine
    2. 7.2 Examples
    3. 7.3 Transitional Representation of Turing Machine
       1. What We Have Learned so Far
       2. Solved Problems
       3. Multiple Choice Questions
       4. Exercises
       5. Fill in the Blanks
17. References
18. Index
19. Back Cover