INTRODUCTION TO THEORY OF AUTOMATA, FORMAL ENGS, AND COMPUTATION

by DEBIDAS GHOSH

Overview

The theory of computation or automata and formal languages assumes significance as it has a wide range of applications in complier design, robotics, Artificial Intelligence (AI), and knowledge engineering. This compact and well-organised book provides a clear analysis of the subject with its emphasis on concepts which are reinforced with a large number of worked-out examples. The book begins with an overview of mathematical preliminaries. The initial chapters discuss in detail the basic concepts of formal languages and automata, finite automata, regular languages and regular expressions, and properties of regular languages. The text then gives a detailed description of context-free languages, pushdown automata and computability of the Turing machine, with its complexity and recursive features. The book concludes by giving clear insights into the theory of computability and computational complexity. This text is primarily designed for undergraduate (BE/B.Tech.) students of computer science and engineering (CSE) and information technology (IT), postgraduate students (M.Sc.) of computer science, and Master of Computer Applications (MCA). FeaturesOne complete chapter devoted to a discussion on undecidable problems. Numerous examples illustrate the concepts. Exercises at the end of each chapter. Theories with proofs.

Product Details

ISBN-13:	9788120348073
Publisher:	PHI Learning
Publication date:	08/21/2013
Sold by:	Barnes & Noble
Format:	eBook
File size:	2 MB

About the Author

Debidas Ghosh (PhD) is Professor of Computer Science and Engineering (CSE) Department, National Institute of Technology (NIT), Durgapur for more than 25 years. He has been the Founder-Head and Head of the Department of Computer Science and Engineering for five terms. Professor Ghosh has also been Founder-Head and Head of the Department for two terms of Computer Applications Department (BCA/MCA) of the Institute. Besides, he is a former Director of NIT, Durgapur; he also served KIIT University, Bhubaneswar as its Pro-Vice-Chancellor.

His areas of interest include Theoretical Computer Science, Crypto-graphy, and Algorithmic Mechanism Design. He has published more than 50 research publications and presented research papers in various international conferences held in USA, China, Israel, UK, France and Denmark.

Table of Contents

Preface • Acknowledgements

1. Preliminary Mathematical Review

2. Three Basic Concepts: Grammar, Languages and Automata

3. Finite Automata

4. Regular Languages and Regular Grammars

5. Properties of Regular Languages

6. Context-Free Languages

7. Pushdown Automata

8. Properties of Context-Free Languages

9. Turing Machine

10. Other Models of Turing Machines

11. Hierarchy of Formal Languages and Linear Bounded Automata

12. Undecidability

13. Theory of Computability

14. Computational Complexity

Index