Formal Languages and Automata Theory, As per AICTE

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.

About the Author

Dr Basavaraj S. Anami is currently the Principal of K.L.E. Institute of Technology, Hubli, Karnataka. He is one amongst very few who propagated Computer Science education in North Karnataka; and is a BoS member in Computer Science in Visvesvaraya Technological University, Belgaum, Karnataka. Moreover, he has served as a Visiting Professor at Saginaw Valley State University, Michigan

Table of Contents

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

Empower Your Learning with Wiley’s AI Buddy

Formal Languages and Automata Theory, As per AICTE

Description

About the Author