Formal Languages and Automata Theory, As per AICTE

Basavaraj S.Anami, Karibasappa K.G.

ISBN: 9788126512126

252 pages

INR 599

Description

This book adopts a holistic approach to learning from fundamentals of formal languages to undecidability problems. Its organization follows the order in which the course is taught over the years, and is well-accepted by the student community. The contents of each topic help even a novice reader to follow the material and motivate the reader to read and understand rather than remember and reproduce. The book is divided into nine chapters that are arranged in the order in which the course is taught over the years, and well-accepted by the student community. The theorems are limited to requirement of an undergraduate level, and the proofs are kept as simple as possible. The concepts are illustrated through fair number of examples.

Preface

 

1 Mathematical Preliminaries for Finite Automata and Formal Languages

1.1 Sets

1.2 Relations and Functions

1.3 Graphs and Trees

1.4 Mathematical Induction

1.5 Mathematical Logic

1.6 Formal Language

1.7 Chomsky Hierarchy Languages (CHL)

1.8 Automata Theory

1.9 Applications of Automata

 

2 Regular Expressions and Regular Languages

2.1 Regular Expressions

2.2 Regular Languages and Regular Grammar

2.3 Applications of REs

 

3 Finite State Automata

3.1 Deterministic Finite Automata

3.2 Non-Deterministic Finite Automata

3.3 NFA and Regular Expressions

3.4 Conversion of Finite Automata to Regular Expression

3.5 Conversion of NFA to DFA

3.6 NFA with e-Transitions (e-NFA)

3.7 Conversion from e-NFA to NFA

3.8 Conversion from e-NFA to DFA

3.9 Output Associated with Finite Automata

3.10 Moore and Mealy Machines

3.11 Minimization of Automata

3.12 Applications of FA

 

4 Properties of Regular Languages

4.1 Pumping Lemma for Regular Languages

4.2 Closure Properties of Regular Languages

4.3 Decision Properties of Regular Languages

 

5 Context-Free Grammars and Languages

5.1 Definition of Context-Free Grammar

5.2 Leftmost and Rightmost Derivations

5.3 Derivation Tree

5.4 Ambiguity in Grammar

5.5 Parsing

5.6 Removal of Useless Symbols and Unit Productions

5.7 Removal of e-productions

5.8 Normal Forms for CFG Specification

 

6 Pushdown Automata

6.1 Definition of PDA

6.2 Non-deterministic PDA

6.3 Instantaneous Description of PDA

6.4 Graphical Notations for PDA

6.5 Languages of PDA

6.6 Equivalence of PDAS and CFGS

6.7 Deterministic PDA

 

7 Properties of Context-Free Languages

7.1 Pumping Lemma for CFLs

7.2 Applications of Pumping Lemma

7.3 Linear Context-Free Languages

7.4 Ogden’s Lemma and its Applications

7.5 Closure Properties of CFLS

7.7 Decision Properties of CFLs

 

8 Turing Machines

8.1 Problems that Computers Cannot Solve

8.2 Basic Model of the Turing Machine

8.3 Representation of a Turing Machine

8.4 Language of Turing Machine

8.5 Computable Languages and Functions

8.6 Programming Techniques of Turing Machine

8.7 Variations of Turing Machines

8.8 Universal Turing Machine

 

9 Undecidability

9.1 Computers and Turing Machine

9.2 Recursively Enumerable Languages

9.3 Halting Problem

9.4 Rice theorem

9.5 Post-Correspondence Problem

 

Summary

Key Terms

Exercises

Model Question Paper 1

Model Question Paper 2

Bibliography

Index