Contents – Introduction to Automata Theory, Formal Languages and Computation

Contents

Foreword

Preface

Acknowledgements

About the Author

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

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

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 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 ∈(null) Move

3.9.1 Usefulness of NFA with Move

3.9.2 Conversion of an NFA with Moves to DFA without 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.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 Application 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

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

5. Regular Expression

Introduction

5.1 Basics of Regular Expression

5.1.1 Some Formal Recursive Definitions of RE

5.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 transition

5.5.2 Direct Conversion of RE to DFA

5.6 NFA with ∈ Move and Conversion to DFA by ∈ -Closure Method

5.6.1 Conversion of an NFA with 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 Application of Regular Expression

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

GATE Questions

Fill in the Blanks

Exercise

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

6.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

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

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

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

9.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

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

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ödel Number

11.4.1 Russell’s Paradox

11.5 Ackermann’s Function

11.6 Minimalization

11.7 μ Recursive

11.7.1 Properties of a μ Recursive Function

11.8 λ Calculus

11.9 Cantor Diagonal Method

11.10 The Rice Theorem

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

Exercise

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 (Ω) Notation

12.2.3 Theta Notation (Θ)

12.2.4 Little-oh Notation (o)

12.2.5 Little Omega Notation (ω)

12.3 Problems and Its Classification

12.4 Different Types of Time Complexity

12.4.1 Constant Time Complexity

12.4.2 Logarithmic Time Complexity

12.4.3 Linear Time Complexity

12.4.4 Quasilinear Time Complexity

12.4.5 Average Case Time Complexity

12.4.6 Polynomial Time Complexity

12.4.7 Super Polynomial Time Complexity

12.5 The Classes P

12.6 Non-polynomial Time Complexity

12.7 Polynomial Time Reducibility

12.8 Deterministic and Non-deterministic Algorithm

12.8.1 Tractable and Intractable Problem

12.9 P = NP?—The Million Dollar Question

12.10 SAT and CSAT Problem

12.10.1 Satisfiability Problem (SAT)

12.10.2 Circuit Satisfiability Problem (CSAT)

12.11 NP Complete

12.11.1 Cook–Levin Theorem

12.12 NP Hard

12.12.1 Properties of NP Hard Problems

12.13 Space Complexity

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

GATE Questions

Exercise

13. Basics of Compiler Design

Introduction

13.1 Definition

13.2 Types of Compiler

13.2.1 Difference Between Single Pass and Multi Pass Compiler

13.3 Major Parts of Compiler

13.3.1 Lexical Analysis

13.3.2 Syntax Analysis

13.3.3 Parser

What We Have Learned So Far

Multiple Choice Questions

GATE Questions

Exercise

14. Advance Topics Related to Automata

Introduction

14.1 Matrix Grammar

14.2 Probabilistic Finite Automata

14.2.1 String Accepted by a PA

14.3 Cellular Automata

14.3.1 Characteristics of Cellular Automata

14.3.2 Applications of Cellular Automata

References