Formal Languages and Automata Theory

Formal Languages and Automata Theory

by K.V.N. Sunitha
Released April 2015
Publisher(s): Pearson Education India
ISBN: 9789332558274

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


Formal Languages and Automata Theory deals with the mathematical abstraction model of computation and its relation to formal languages. This book is intended to expose students to the theoretical development of computer science. It also provides conceptual tools that practitioners use in computer engineering. An assortment of problems illustrative of each method is solved in all possible ways for the benefit of students. The book also presents challenging exercises designed to hone the analytical skills of students.

Table of contents

  1. Cover
  2. Title page
  3. Brief Contents
  4. Contents
  5. Preface
  6. Acknowledgements
  7. List of Important Symbols
  8. List of Important Abbreviations
  9. About the Authors
  10. 1. Mathematical Preliminaries and Formal Languages
    1. 1.1 Set Theory
      1. 1.1.1 Describing a Set
      2. 1.1.2 Empty Set
      3. 1.1.3 Identity and Cardinality
      4. 1.1.4 Subset
      5. 1.1.5 Power Sets
      6. 1.1.6 Operations on Sets: Union, Intersection
      7. 1.1.7 Set Theoretic Equalities
      8. 1.1.8 Sequence versus Set
      9. 1.1.9 Ordered Pairs
      10. 1.1.10 Cartesian Product
    2. 1.2 Relations
      1. 1.2.1 Binary Relation
      2. 1.2.2 Domain and Range of Relation
      3. 1.2.3 Operations on Relations
      4. 1.2.4 Properties of Relations
    3. 1.3 Functions
      1. 1.3.1 Definitions
      2. 1.3.2 Types of Functions
    4. 1.4 Alphabet, String and Language
      1. 1.4.1 Operations on Language
      2. 1.4.2 Grammars
      3. 1.4.3 Types of Grammars–Chomsky Hierarchy
    5. 1.5 Graphs and Trees
      1. 1.5.1 Directed Graph
      2. 1.5.2 Undirected Graph
      3. 1.5.3 Trees
    6. 1.6 Theorem Proving
      1. 1.6.1 Proof by Induction
      2. 1.6.2 Proof by Contradiction
      3. 1.6.3 Proof by Example
    7. Summary
    8. Short Answers
    9. Fill in the Blanks
    10. Objective Question Bank
    11. Exercises
  11. 2. Finite Automata
    1. 2.1 Finite-state Machine
      1. 2.1.1 Finite-Automaton Model
      2. 2.1.2 Properties of Transition Function ‘χ’
      3. 2.1.3 Transition Diagram
      4. 2.1.4 Transition Table
    2. 2.2 Language Acceptance
    3. 2.3 Two Types of Finite Automata
      1. 2.3.1 Deterministic Finite Automata (DFA)
      2. 2.3.2 Non-deterministic Finite Automaton (NFA)
      3. 2.3.3 Acceptance of NFA
    4. 2.4 Equivalence of DFAs and NFAs
    5. 2.5 Converting NFA (MN) to DFA (MD)—Subset Construction
    6. 2.6 NFA with Epsilon-(ε) Transitions
      1. 2.6.1 Epsilon Closure (ε-closure)
      2. 2.6.2 Eliminating ε-Transitions
      3. 2.6.3 Converting NFA with ε-Transition to NFA without ε-Transition
      4. 2.6.4 Converting NFA with ε-Transition to DFA
    7. 2.7 Comparison Method for Testing Equivalence of Two FAs
    8. 2.8 Reduction of Number of States in FA
      1. 2.8.1 Indistinguishable States
      2. 2.8.2 Equivalent Classes
      3. 2.8.3 Minimization of DFA
      4. 2.8.4 Minimization of DFA Using Myhill Nerode Theorem
    9. 2.9 Finite Automata with Output
      1. 2.9.1 Moore Machine
      2. 2.9.2 Mealy Machine
      3. 2.9.3 Equivalence Between Moore and Mealy Machines
      4. 2.9.4 Interconversions Between Machines
    10. 2.10 Applications of Finite Automata with Output
      1. 2.10.1 The Full-adder
      2. 2.10.2 The String Sequence Detector
    11. Solved Problems
    12. Summary
    13. Short Answers
    14. Fill in the Blanks
    15. Objective Question Bank
    16. Exercises
  12. 3. Regular Languages and Regular Grammars
    1. 3.1 Regular Expressions
    2. 3.2 Regular Sets
    3. 3.3 Identity Rules for Regular Expressions
    4. 3.4 Algebraic Laws for Regular Expressions
    5. 3.5 Equivalence of Finite Automata with Regular Expressions
    6. 3.6 Constructing Regular Expression for Given DFA
      1. 3.6.1 Arden’s Theorem
      2. 3.6.2 Arden’s Theorem in Construction of RE
      3. 3.6.3 Construction of RE Using Generalized NFA
    7. 3.7 Pumping Lemma of Regular Expressions
      1. 3.7.1 Formal Definition of the Pumping Lemma
    8. 3.8 Regular Grammar
      1. 3.8.1 Equivalence of Regular Grammar and Finite Automata
      2. 3.8.2 Converting Finite Automaton to Regular Grammar
    9. 3.9 Closure Properties of Regular Sets
    10. 3.10 Applications of Regular Expressions
      1. 3.10.1 Lexical Analysis
      2. 3.10.2 Finding Patterns
    11. 3.11 Decision Properties of Regular Languages
      1. 3.11.1 Conversion from NFA to DFA
      2. 3.11.2 Emptiness Membership and Equivalence
    12. Solved Problems
    13. Summary
    14. Short Answers
    15. Fill in the Blanks
    16. Objective Question Bank
    17. Exercises
  13. 4. Context Free Grammars and Context Free Languages
    1. 4.1 Context Free Grammars
    2. 4.2 Derivation of CFGs
    3. 4.3 Understanding the Language Defined by Grammars
      1. 4.3.1 Leftmost and Rightmost Derivations
      2. 4.3.2 Derivation Tree
      3. 4.3.3 Equivalence of Parse Trees and Derivations
    4. 4.4 Ambiguous Grammar
      1. 4.4.1 Removing Ambiguity
      2. 4.4.2 Inherent Ambiguity
    5. 4.5 Simplification of Grammars
      1. 4.5.1 Elimination of Useless Symbols
      2. 4.5.2 Elimination of ε-Productions
      3. 4.5.3 Eliminating Unit Productions
    6. 4.6 Normal Forms
      1. 4.6.1 The Chomsky Normal Form
      2. 4.6.2 The Greibach Normal Form
    7. 4.7 Pumping Lemma for CFL
      1. 4.7.1 Lemma
    8. 4.8 Decision Algorithms for CFLs
      1. 4.8.1 Finiteness and Infiniteness
    9. 4.9 Membership
    10. 4.10 Closure Properties of CFLs
    11. 4.11 Applications of CFG
    12. Solved Problems
    13. Summary
    14. Short Answers
    15. Fill in the Blanks
    16. Objective Question Bank
    17. Exercises
  14. 5. Push Down Automata
    1. 5.1 Pushdown Automata
      1. 5.1.1 Graphical Representation of PDA
      2. 5.1.2 Instantaneous Description of PDA
      3. 5.1.3 Language Acceptance by PDA
    2. 5.2 Equivalence of Acceptance of Final State and Empty Stack
    3. 5.3 Types of PDAs
      1. 5.3.1 Deterministic PDA
      2. 5.3.2 Closure Properties of DCFL
      3. 5.3.3 Decision Properties of DCFLs
      4. 5.3.4 DPDA and Regular Languages
      5. 5.3.5 DPDA and Ambiguous Grammar
    4. 5.4 Equivalence of PDA’s and CFG’s
      1. 5.4.1 Constructing PDA for Given CFG
      2. 5.4.2 Constructing CFG for the Given PDA
    5. 5.5 Two-stack PDA
    6. 5.6 Applications of PDA
      1. 5.6.1 PDA as a Parser
      2. 5.6.2 Top-down Parser Using the PDA
    7. Solved Problems
    8. Summary
    9. Short Answers
    10. Fill in the Blanks
    11. Objective Question Bank
    12. Exercises
  15. 6. Turing Machines
    1. 6.1 Turing Assumptions
      1. 6.1.1 Instantaneous Description
      2. 6.1.2 Turing Machine as Language Accepter
    2. 6.2 Turing Machine as a Computational Machine
    3. 6.3 Techniques for Turing Machine Construction
      1. 6.3.1 Storage in Finite Control
      2. 6.3.2 Multi-track Tape
      3. 6.3.3 Checking off Symbols
      4. 6.3.4 Subroutines
      5. 6.3.5 Shifting Over
    4. 6.4 Types of Turing Machines
      1. 6.4.1 Non-deterministic Turing Machines
      2. 6.4.2 Turing Machines with Two-dimensional Tapes
      3. 6.4.3 Turing Machines with Multiple Tapes
      4. 6.4.4 Turing Machines with Multiple Heads
      5. 6.4.5 Turing Machines with Infinite Tape
    5. 6.5 Church’s Thesis
    6. 6.6 Turing Machines as Enumerators
    7. 6.7 Universal Turing Machine
    8. 6.8 Counter Machine
    9. 6.9 Recursive and Recursively Enumerable Languages
    10. 6.10 Linear Bound Automata and Context Sensitive Language
      1. 6.10.1 Equivalence of LBA’s and CSG’s
    11. Solved Problems
    12. Summary
    13. Short Answers
    14. Fill in the Blanks
    15. Objective Question Bank
    16. Exercises
  16. 7. Undecidability and Computability
    1. 7.1 Decision Problems
    2. 7.2 Decidability and Decidable Languages
      1. 7.2.1 Decidable Problems Concerning Regular Languages
      2. 7.2.2 Decidable Problems Concerning Context Free Languages
    3. 7.3 Halting Problem
      1. 7.3.1 The Halting Problem for Turing Machines
    4. 7.4 Diagonalization Method
      1. 7.4.1 Undecidable Problems
    5. 7.5 Post’s Correspondence Problem
      1. 7.5.1 The Undecidability of Post’s Correspondence Problem
      2. 7.5.2 Modified Version of PCP
    6. 7.6 Reducibility
      1. 7.6.1 Properties
      2. 7.6.2 Mapping Reducibility
      3. 7.6.3 Formal Definition of Mapping Reducibility
    7. 7.7 Recursion Theorem
      1. 7.7.1 Applications and Uses of Recursion
    8. 7.8 Rice’s Theorem
    9. 7.9 Ackermann’s Function
    10. Solved Problems
    11. Summary
    12. Short Answers
    13. Fill in the Blanks
    14. Objective Question Bank
    15. Exercises
  17. 8. Non-deterministic Polynomial Completeness
    1. 8.1 NP-hard and NP-complete
      1. 8.1.1 Classification of Problems
    2. 8.2 P Problems
    3. 8.3 NP Problems
    4. 8.4 Tractable Problems
    5. 8.5 NP-complete
    6. 8.6 NP-hard
    7. 8.7 Examples of Problems in Different Classes
    8. 8.8 NP-completeness
    9. 8.9 Reduction
      1. 8.9.1 Computational Complexity
      2. 8.9.2 0–1 Knapsack Problem
      3. 8.9.3 Computational Complexity
    10. Solved Problems
    11. Summary
    12. Short Answers
    13. Fill in the Blanks
    14. Objective Question Bank
    15. Exercises
  18. 9. LR(k) and LL(1) Grammars
    1. 9.1 LL(1) Grammar
    2. 9.2 Rules for Verifying Whether the Given Grammar Is LL(1) or Not
    3. 9.3 LR(K) Grammars
    4. 9.4 Properties of LR(k) Grammars
    5. 9.5 Construction of LR(0) Items for Context Free Grammars
    6. 9.6 Definition of LR(0) Grammar
    7. 9.7 LR(1) Grammar
    8. Solved Problems
    9. Summary
    10. Short Answers
    11. Fill in the Blanks
    12. Objective Question Bank
    13. Exercises
  19. Appendix A: Proposition and Predicate Logic
    1. A.1 Propositions
    2. A.2 Connectives
    3. A.3 Well-Formed Formula
    4. A.3.1 Truth Table for a Well-formed Formula
    5. A.4 Logical Identities
    6. A.5 Normal Forms of Well-formed Formals
    7. A.5.1 Construction to Obtain a Disjunctive Normal Form of a Given Formula
    8. A.6 Principal Disjunctive Normal Form
    9. A.6.1 Construction to Obtain the Principal Disjunctive Normal Form of a Given Formula
    10. A.7 Predicate Calculus
    11. A.8 Universal and Existential Quantifier
    12. A.9 Well-formed Formulas of Predicate Calculus
    13. A.10 Rules of Inference for Predicate Calculus
    14. Summary
  20. Appendix B: Frequently Asked University Questions with Solutions
    1. Part A - Brief Questions
    2. Part B - Detailed Questions
  21. References
  22. Copyright

Product information

  • Title: Formal Languages and Automata Theory
  • Author(s): K.V.N. Sunitha
  • Release date: April 2015
  • Publisher(s): Pearson Education India
  • ISBN: 9789332558274