Contents

About the Author

Foreword

Preface

Acknowledgements

 

 

1.  Finite State Machine

1.1 Basics of Automata

1.2 Finite State Machine

1.3 State Equivalence and Minimization of Machine

1.4 Incompletely Specified Machine and Minimal Machine

1.5 Merger Graph and Compatibility Graph

1.6 Finite Memory and Definite Memory Machine

1.7 Information Lossless Machine and Inverse Machine

1.8 Inverse Machine

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

Exercises

Fill in the Blanks

 

2.  Language and Grammar

2.1 Basic Terminology and Definitions

2.2 Grammar and Language

2.3 Chomsky Hierarchy

2.4 Examples

2.5 Context-sensitive Grammar

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

Exercises

Fill in the Blanks

 

3.  Finite Automata

3.1 Basics About Finite Automata

3.2 Transitional System

3.3 Deterministic Finite Automata and Non-Deterministic Finite Automata

3.4 NFA with Null Move

3.5 Dead State

3.6 Finite Automata with Output

3.7 Conversion of Moore To Mealy Machine by Tabular Format

3.8 Conversion of Mealy to Moore Machine by Tabular Format

3.9 Conversion of Moore to Mealy Machine by Transitional Format

3.10 Conversion of Mealy to Moore Machine by Transitional Format

3.11 Minimization of Finite Automata

3.12 Myhill-Nerode Theorem

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

Exercises

Fill in the Blanks

 

4.  Regular Expression

4.1 Basics of Regular Expression

4.2 Arden Theorem

4.3 Construction of Finite Automata Equivalent to a Regular Expression

4.4 NFA With Move and Conversion to DFA By - Closure Method

4.5 Equivalence of Two Finite Automata and Two Regular Expressions

4.6 Construction of Regular Grammar from a Regular Expression

4.7 Pumping Lemma and its Application

4.8 Closure Properties of Regular Set

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

Exercises

Fill in the Blanks

 

5.  Context Free Grammar

5.1 Context Free Grammar: Definition and Examples

5.2 Derivation and Parse Tree

5.3 Ambiguity

5.4 Left Recursion and Left Factoring

5.5 Simplification of CFG

5.6 Normal Form

5.7 Constructing FA from Regular Grammar

5.8 Closure Properties of CFL

5.9 Pumping Lemma for CFL

5.10 Ogden's Lemma for CFL

5.11 Decision Algorithms

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

Exercises

Fill in the Blanks

 

6.  Pushdown Automata

6.1 Basics of Pushdown Automata

6.2 Acceptance by a PDA

6.3 Examples

6.4 Deterministic PDA and Non-Deterministic PDA

6.5 Pushdown Automata from Context Free Grammar

6.6 Graphical Notation for PDA

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

Exercises

Fill in the Blanks

 

7.  Turing Machine

7.1 Basic of Turing Machine

7.2 Examples

7.3 Transitional Representation of Turing Machine

What We Have Learned So Far

Solved Problems

Multiple Choice Questions

Exercises

Fill in the Blanks

References

Index