You are previewing Express Learning: Automata Theory and Formal Languages.
O'Reilly logo
Express Learning: Automata Theory and Formal Languages

Book Description

Express Learning is a series of books designed as quick reference guides to important undergraduate computer courses. The organized and accessible format of these books allows students to learn important concepts in an easy-to-understand, question-and-answer format. These portable learning tools have been designed as one-stop references for students to understand and master the subjects by themselves.

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