Introduction to Formal Languages, Automata Theory and Computation

Introduction to Formal Languages, Automata Theory and Computation

Released April 2009
Publisher(s): Pearson India
ISBN: 9788131723562

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Introduction to Formal Languages, Automata Theory and Computation presents the theoretical concepts in a concise and clear manner, with an in-depth coverage of formal grammar and basic automata types.

Table of contents

  1. Copyright
    1. Dedicated to
  2. About the Authors
  3. Preface
  4. Acknowledgements
  5. 1. Preliminaries
    1. 1.1. Sets, Relations, and Functions
      1. Sets
      2. Sequences and Tuples
      3. Relations and Functions
      4. Ordered Pairs
      5. Closures
      6. Finite and Infinite Sets
    2. 1.2. Methods of Proof
      1. Mathematical Induction
      2. Strong Mathematical Induction
      3. Pigeonhole Principle
      4. Diagonalization Principle
    3. 1.3. Graphs
    4. 1.4. Languages: Basic Concepts
      1. Asymptotic Behavior of Functions
    5. Problems and Solutions
    6. Exercises
  6. 2. Grammars
    1. 2.1. Definitions and Classification of Grammars
      1. Derivation Trees
    2. 2.2. Ambiguity
    3. 2.3. Simplification of CFGs
      1. Removing Useless Productions
      2. Algorithm GENERATING
      3. Algorithm REACHABLE
      4. ε-rule Elimination Method
      5. Algorithm NULL
      6. Basis
      7. Induction
      8. Procedure to Eliminate Unit Rules
      9. Algorithm UNIT-PAIR
    4. 2.4. Normal Forms
      1. Weak Chomsky Normal Form
      2. Chomsky Normal Form
      3. Strong Chomsky Normal Form
      4. Greibach Normal Form
        1. Technique 1
        2. Technique 2
    5. Problems and Solutions
    6. Exercises
  7. 3. Finite State Automata
    1. 3.1. Deterministic Finite State Automaton (DFSA)
    2. 3.2. Non-deterministic Finite State Automaton (NFSA)
      1. Basis
      2. Induction
      3. NFSA with ε-transitions
      4. Basis
      5. Induction
    3. 3.3. Regular Expressions
      1. Algorithm
    4. Problems and Solutions
    5. Exercises
  8. 4. Finite State Automata: Characterization, Properties, and Decidability
    1. 4.1. FSA and Regular Grammars
    2. 4.2. Pumping Lemma for Regular Sets
      1. Remarks on Pumping Lemma
    3. 4.3. Closure Properties
    4. 4.4. Decidability Theorems
    5. Problems and Solutions
    6. Exercises
  9. 5. Finite State Automata with Output and Minimization
    1. 5.1. Myhill-Nerode Theorem
      1. Minimization of DFSA
      2. Algorithm to Find Minimum DFSA
    2. 5.2. Finite Automata with Output
    3. Problems and Solutions
    4. Exercises
  10. 6. Variants of Finite Automata
    1. 6.1. Two-Way Finite Automata
      1. Basis
      2. Induction
    2. 6.2. Multihead Finite State Automata
    3. 6.3. Probabilistic Finite Automata
    4. 6.4. Weighted Finite Automata and Digital Images
      1. 6.4.1. Finite Automata and Black-White Images
      2. 6.4.2. Weighted Finite Automata and Gray-Scale Images
        1. Representation of Gray-Scale Images
      3. 6.4.3. Inferencing and De-Inferencing
        1. De-Inferencing
        2. Algorithm: De_Infer_WFA
        3. Inferencing
        4. Algorithm Infer_WFA
        5. Approximate Representation
        6. Compression
        7. Observation
      4. 6.4.4. Transformations on Digital Images
        1. Weighted Finite Transducers
        2. Scaling
        3. Translation
        4. Representation of 3-Dimensional Objects
    5. Problems and Solutions
    6. Exercises
  11. 7. Pushdown Automata
    1. 7.1. The Pushdown Automaton
    2. 7.2. Equivalence between Acceptance by Empty Store and Acceptance by Final State
    3. 7.3. Equivalence of CFG and PDA
      1. Basis
      2. Induction
      3. Basis
      4. Induction
      5. Basis
      6. Induction
      7. Basis
      8. Induction
    4. Problems and Solutions
    5. Exercises
  12. 8. Context-Free Grammars–Properties and Parsing
    1. 8.1. Pumping Lemma for CFL
    2. 8.2. Closure Properties of CFL
    3. 8.3. Decidability Results for CFL
      1. Membership Problem for CFL
      2. CYK Algorithm
    4. 8.4. SubFamilies of CFL
    5. 8.5. Parikh Mapping and Parikh’s Theorem
      1. Semi-linear Sets
      2. Parikh Mapping
      3. Application of Parikh’s Theorem
    6. 8.6. Self-embedding Property
    7. 8.7. Homomorphic Characterization
    8. Problems and Solutions
    9. Exercises
  13. 9. Turing Machines
    1. 9.1. Turing Machine as an Acceptor
    2. 9.2. Turing Machine as a Computing Device
    3. 9.3. Techniques for Turing Machine Construction
      1. 1. Considering the state as a tuple
      2. 2. Considering the tape symbol as a tuple
      3. 3. Checking off symbols
      4. 4. Shifting over
      5. 5. Subroutines
    4. Problems and Solutions
    5. Exercises
  14. 10. Variations of Turing Machines
    1. 10.1. Generalized Versions
      1. 10.1.1. Two-Way Infinite Tape TM
      2. 10.1.2. Multi-tape TM
      3. 10.1.3. Multi-head TM
      4. 10.1.4. Non-deterministic Turing Machine (NTM)
      5. 10.1.5. Two-Dimensional TM
    2. 10.2. Restricted Turing Machines
    3. 10.3. Turing Machines as Enumerators
    4. 10.4. Equivalence Between Turing Machines and Type 0 Languages
    5. 10.5. Linear-Bounded Automata
    6. 10.6. Gödel Numbering
      1. 10.6.1. Gödel Numbering of Sequences of Positive Integers
      2. 10.6.2. Gödel Number of Strings
      3. 10.6.3. Gödel Number of Undirected Graphs
    7. Problems and Solutions
    8. Exercises
  15. 11. Universal Turing Machine and Decidability
    1. 11.1. Encoding and Enumeration of Turing Machines
      1. Enumeration of TMs
    2. 11.2. Recursive and Recursively Enumerable Sets
    3. 11.3. Universal Turing Machine
      1. The Halting Problem
    4. 11.4. Problems, Instances, and Languages
    5. 11.5. Rice’s Theorem
    6. 11.6. Reduction of Problems to Show Undecidability
    7. 11.7. Post’s Correspondence Problem
      1. Modified PCP (MPCP)
    8. 11.8. Computable Functions
      1. Primitive Recursive Function
      2. Primitive Recursive Predicates
      3. The Busy Beaver Problem
    9. Problems and Solutions
    10. Exercises
  16. 12. Time and Space Complexity
    1. 12.1. The RAM Model
      1. Comparison of RAM and TM
      2. Simulation of RAM by a TM
      3. Simulation of TM by RAM
      4. Problems, Instances, and Languages
    2. 12.2. Time and Tape Complexity of Turing Machines
      1. Space Complexity
      2. Time Complexity
      3. Assumptions
      4. Non-deterministic Time and Space Complexity
      5. Complexity Classes
      6. Space Hierarchy
      7. Some Results on Complexity Classes
      8. Polynomial Time and Space
      9. Intractable Problems
      10. Reducibility and Complete Problems
      11. Satisfiability-Cook’s Theorem
      12. Beyond NP-completeness
    3. Problems and Solutions
    4. Exercises
  17. 13. Recent Trends and Applications
    1. 13.1. Regulated Re-writing
      1. Matrix Grammar
        1. Programmed Grammar
        2. Random Context Grammar
        3. Time-Varying Grammar
        4. Regular Control Grammars
        5. Indian Parallel Grammars
    2. 13.2. Marcus Contextual Grammars
      1. 13.2.1. Definitions and Examples
        1. Notations
      2. 13.2.2. Generative Capacity
      3. 13.2.3. Closure and Decidability Properties of Contextual Languages
    3. 13.3. Lindenmayer Systems
      1. Extended System
      2. Systems with Interactions
      3. Applications
      4. Two-Dimensional Generation of Patterns
      5. Fractals Generated by L-systems
      6. Interpretation of a String
      7. Interpolation
      8. Candies
      9. Generation of Plant Structure
    4. 13.4. Grammar Systems and Distributed Automata
      1. Grammar Systems
      2. 13.4.1. CD Grammar Systems
      3. 13.4.2. PC Grammar Systems
      4. 13.4.3. Distributed Automata
      5. Distributed Nondeterministic FSA
        1. t-mode acceptance
        2. *-mode acceptance
        3. =k-mode (≤ k-mode, ≥ k-mode) acceptance
      6. Power of Acceptance of Different Modes
      7. Distributed Nondeterministic Pushdown Automata
        1. t-mode acceptance
        2. *-mode acceptance
        3. =k-mode(≤ k-mode, ≥ k-mode) acceptance
      8. Acceptance Power of NPDA
      9. Acceptance by Empty Store
      10. Equivalence
      11. Distributed k-turn PDA
  18. 14. New Models of Computation
    1. 14.1. DNA Computing
      1. Splicing Operation
      2. Iterated Splicing
    2. 14.2. Membrane Computing
      1. Operations with Strings and Languages
      2. P Systems with Labeled Membranes
      3. Rewriting P Systems
      4. P Systems with Sequential Rewriting
      5. P Systems based on Sequential Rewriting with Membranes of Variable Thickness
      6. P Systems with Replicated Rewriting
      7. Solving SAT and HPP
      8. P Systems with Active Membranes
      9. Solving SAT in Linear Time
      10. Tissue P Systems
  19. Multiple Choice Questions (Set I)
    1. Answers
  20. Multiple Choice Questions (Set II)
    1. Answers
  21. Bibliography
  22. Illustrations

Product information

  • Title: Introduction to Formal Languages, Automata Theory and Computation
  • Author(s):
  • Release date: April 2009
  • Publisher(s): Pearson India
  • ISBN: 9788131723562