Book

Theory of automata, formal languages and computation

---

This book deals with a fascinating and important subject which has the
fundamentals of computer hardware, software and some of their applications.
This book is intended as an introductory graduate text in computer science
theory. I have taken care to present the material very clearly and interestingly.
As an introductory subject to computer science, this book has been written
with major stress on worked examples. Chapter 0 covers the basics required
for this subject viz., sets, relations, functions, graphs, trees, languages, and
fundamental proof techniques.
Chapter 1 deals with the different aspects of Deterministic Finite
Automata (DFA) and Non-Deterministic Finite Automata (NFA). A brief
introduction to pumping lemma and some theorems relating to Regular Sets
have also been given.
Chapter 2 covers the concepts relating to context free grammar viz.,
derivation trees, parsing, ambiguity, and normal forms. Chapter 3 deals with
Pushdown Automata and their relation to Context-Free Grammar with some
introduction to decision algorithms.
Chapter 4 deals with the Turing Machine model and the variations of
Turing Machines with introduction to Church-Turing Thesis and the concept
of undecidability. Chapter 5 explains the concepts viz., regular grammars,
unrestricted grammars and Chomsky hierarchy of languages.
Chapter 6 deals with the different aspects of computability with an
introduction to formal systems, recursive functions, primitive recursive
functions, and recursion. Chapter 7 covers the various aspect of complexity
theory such as polynomial time algorithms, non-polynomial time algorithm
class P and NP problems.
Chapter 8 covers propositions and predicates with lot of illustrative
examples.
I wish to thank my teachers who helped me to get a good grasp of the
subject and for having motivated me to write this book.
I want to place on record my sincere thanks to my family?Shri. Papu
Antony, my father; Mrs. Maria Daisy, my mother; Mrs. Assumpta Eugene, my
wife; and Ms. E. Catherine Praveena, my only daughter, for their great
patience and prayers while I was writing this book.

---

Availability

Detail Information

Series Title

-

Call Number

511.3 XAV

Publisher

India : New Age International Limited, Publishers, New Delhi., 2005

Collation

xiiii 346 pages

Language

English

ISBN/ISSN

9786611-22-4486

Classification

511.3

Content Type

-

Media Type

-

Carrier Type

-

Edition

1st Edition

Subject(s)

Computer Science Software Engineering
data Science
1. Computer Science 2. Software Engineering 3. Dat
Data Science Information Technology
1. Computer Science 2.software engineering Softwar

Specific Detail Info

-

Statement of Responsibility

S. P. Eugene Xavier

Other version/related

File Attachment

Comments

---

You must be logged in to post a comment