## Description

This book is designed for fundamental courses on automata theory and formal languages. It emphasizes on topics such as mathematical models, finite automata, context-free grammars, pushdown automata, Turing machine, undecidability, computational complexity, P and NP completeness.

• Explains all types of problem solving in formal languages and automata models.

• Presents clear graphical representation for DFA, NDFA, PDA and Turing machine.

## Table of Content

**Chapter 1 Finite Automata**

1.1 Introduction

1.2 Basic Mathematical Notation and Techniques

1.2.1 Formal Proof

1.2.2 Deductive Proofs

1.2.3 If-then Statements

1.2.4 If and only-If Statement

1.2.5 Additional Forms of Proof

1.2.6 Inductive Proofs

1.2.7 Problems in Induction

1.3 Basic Definitions

1.4 Finite State Systems

1.5 Finite Automaton

1.6 Deterministic Finite Automata and Nondeterministic Finite Automata

1.6.1 Deterministic Finite Automata

1.6.2 Nondeterministic Finite Automata

1.7 Finite Automaton with ε-Moves

1.7.1 Nondeterministic Finite Automata with ε-Moves

1.8 Equivalence of NDFA and DFA

1.9 Equivalence of NDFAs with and without ε-Moves

Solved Problems 1.1

Solved Problems 1.2

Solved Problems 1.3

Solved Problems 1.4

Points to Remember

University Questions

**Chapter 2 Regular Expression and Languages**

2.1 Introduction

2.2 Regular Languages

2.3 Regular Expression

2.4 Equivalence of Finite Automaton and Regular Expressions

2.4.1 Conversion of Finite Automata (DFA) to Regular Expressions

Solved Examples 2.1

Solved Examples 2.2

2.4.2 Conversion of Regular Expressions to Finite Automata

Solved Examples 2.3

2.5 Pumping Lemma for Regular Sets

2.6 Problems based on Pumping Lemma

Solved Examples 2.4

2.7 Closure Properties of Regular Languages

2.8 Minimization of DFA

Solved Examples 2.5

Points to Remember

University Questions

**Chapter 3 Context-Free Grammar and Languages**

3.1 Introduction

3.2 Types of Grammar

3.3 Context-Free Grammars and Languages

3.3.1 Context-Free Grammar

3.4 Derivations and Languages

3.5 Ambiguity

3.5.1 Ambiguity in Grammars and Languages

3.5.2 Unambiguous Grammar

3.6 Relationship between Derivation and Derivation Trees

Solved Examples 3.1

Points to Remember

University Questions

**Chapter 4 Pushdown Automata**

4.1 Introduction

4.1.1 Definition of PDA

4.1.2 Graphical Notation for PDA

4.2 Moves

4.3 Instantaneous Descriptions of PDA

4.3.1 Three Important Principles about ID

Solved Examples 4.1

4.4 Language of a PDA

4.4.1 Conversion of Final State and Empty Stack

4.5 Equivalence of PDAs and CFGs

4.5.1 Solved Examples for Conversion of Context-Free Grammar to Pushdown

Automata

4.5.2 Solved Examples for Conversion of Pushdown Automata to Context-Free

Grammar

4.6 Types of PDA

4.6.1 Nondeterministic Pushdown Automata

4.6.2 Deterministic Pushdown Automata

Solved Examples 4.2

Points to Remember

University Questions

**Chapter 5 Properties of Context-Free Languages**

5.1 Introduction

5.2 Simplification of CFG

5.2.1 Elimination of Useless Symbols

5.2.2 Elimination of Unit Productions

5.2.3 Elimination of Null or Epsilon Productions

5.3 Normal Forms

5.3.1 Chomsky Normal Form

5.3.2 Greibach Normal Form

5.3.3 Problems Related to CNF and GNF

5.4 Pumping Lemma for CFL

5.4.1 Problems based on Pumping Lemma

Solved Examples 5.1

5.5 Closure Properties of CFL

Points to Remember

University Questions

**Chapter 6 Turing Machines**

6.1 Introduction

6.1.1 Model of a TM

6.1.2 Move of a Turing Machine

6.1.3 Notation for a Turing Machine

6.1.4 Instantaneous Descriptions for TM: (ID) [Configuration of a TM]

6.1.5 Language of a TM

6.1.6 Representations for TM

6.2 Computable Languages and Functions

Solved Examples 6.1

6.3 Techniques for Turing Machine Construction

6.3.1 Storage in the Finite Control or State

6.3.2 Checking off Symbols

6.3.3 Subroutines

6.3.4 Multiple Tracks

6.4 Multi-Head and Multi-Tape Turing Machines

6.5 Nondeterministic Turing Machine

6.6 The Halting Problem

6.7 Partial Solvability

6.8 Problems about Turing Machine

6.9 Chomskian Hierarchy of Languages

Points to Remember

University Questions

**Chapter 7 Un decidability**

7.1 Unsolvable Problems and Computable Functions

7.2 Primitive Recursive Functions

Solved Examples 7.1

7.3 Recursive and Recursively Enumerable Languages

7.3.1 A Language is not Recursively Enumerable

Solved Examples 7.2

7.3.2 An Un decidable Problem Recursively Enumerable

7.4 Universal Turing Machine (UTM)

7.4.1 Un decidable Problems about Turing Machines

7.4.2 Post Correspondence Problem (PCP)

Solved Examples 7.3

Solved Examples 7.4

Points to Remember

University Questions

**Chapter 8 Measuring and Classifying Complexity**

8.1 Tractable and Intractable Problems

8.2 P and NP Completeness

8.3 Polynomial Time Reductions

Points to Remember

University Questions

Appendix – University Question

## About The Authors

**D Shanthi** is Professor and Head, Department of Computer Science and Engineering at PSNA College of Engineering and Technology, Dindigul, Tamil Nadu. She received her Ph.D. in Computer Science and Engineering from Birla Institute of Technology, Ranchi, India. She has 26 years of teaching experience which includes 16 years of research experience. She has published more than 60 papers in international conferences and journals and also published 10 books in computing and applications.

**N Uma Maheswari **is Professor, Department of Computer Science and Engineering at PSNA College of Engineering and Technology, Dindigul, Tamil Nadu. She received her Ph.D. in Information and Communication Engineering from Anna University, Chennai. She has 18 years of teaching experience which includes 13 years of research experience. She has published 30 papers in international journals, 2 papers in national journals, and presented 32 papers at international conferences and 15 papers at national conferences. She has co-authored a book on Compiler Design published by Yes Dee.

**S Jeyanthi **is Associate Professor, Department of Computer Science and Engineering at PSNA College of Engineering and Technology, Dindigul, Tamil Nadu. She received her Ph.D. in Information and Communication Engineering from Anna University, Chennai. She has totally 14 years of teaching experience which includes 7 years of research experience. She has published 15 papers in international journals, 12 papers in international conferences and 6 papers in national conferences. She has co-authored a book on Compiler Design published by Yes Dee.

## New Product Tab

Here's your new product tab.

## Reviews

There are no reviews yet.