Formal Languages and Automata Theory

Basavaraj S.Anami, Karibasappa K.G.

ISBN: 9788126520107

252 pages

eBook also available for institutional users 

INR 619

Description

Formal Languages and Automata theory presents the theoretical aspects of computer science, and helps define infinite languages in finite ways; construct algorithms for related problems and decide whether a string is in language or not. These are of practical importance in construction of compilers and designing of programming languages, thus establishing the course as a core paper in third/fourth year of various universities. 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 motivate the reader to easily understand the concepts rather than remember and reproduce.

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

Learning Objectives

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

×
  • Name:
  • Designation:
  • Name of Institute:
  • Email:
  • * Request from personal id will not be entertained
  • Moblie:
  • ISBN / Title:
  • ISBN:    * Please specify ISBN / Title Name clearly