Preface

An engineer must ask ‘why’ not ‘how’. The Bachelor of Computer Science and Engineering is not only about learning some application software and some programming languages but also about learning how a programming language works, how a program is compiled and how input is converted to output from the machine hardware level. The theoretical part of Computer Science includes Complexity Analysis, Compiler Construction, verifying correctness of circuits and protocols etc. Automata Theory is one of the core courses in the curriculum of Bachelor of Technology of Computer Science or Information Technology under any university. It is said that Automata Theory is “the study of abstract machine and the problems which they are able to solve”. This book is a part of series named Express Learning Series which has a number of books designed as quick reference.

Students have to study the two parts subject in Automata Theory and Theory of Computation. Automata Theory contains Switching Theory, Machine Construction, Machine Checking and Minimization whereas the Theory of Computation includes different types of languages and grammars according to Chomsky Hierarchy. During my teaching career, I have felt that students need a complete book containing both the sections, a large number of solved problems, multiple choice questions and useful exercise to practice. This book is written to fullfill this requirement of students. It is written in simple language keeping in mind the level of undergraduate students . The theory part is described with suitable examples and useful diagrams. Solved problems are included to explain the theory. At the end of each chapter a number of multiple choice questions related to the topic are which will help students preparing themselves for competitive examinations like GATE, NET. The book contains 7 chapters.

Chapter 1 deals with finite state machine, machine construction, machine minimization which are the main parts of automata theory. Chapter 2 describes different types of languages and grammar according to the classification by Chomsky. This chapter is the root part of theory of computation. Chapter 3 deals with introduction of finite automata, deterministic and non-deterministic finite automata, mealy machine, Moore machine and minimization of finite automata. Chapter 4 describes regular expressions Arden's Theorem, Pumping Lemma for Regular Expression. Chapter 5 deals with context free grammar, simplification of context free grammar, different normal form. Chapter 6 deals with push down automata, construction of push down automata directly from context free grammar. Chapter 7 describes the Turing Machine.

I will appreciate suggestions for further improvement of the book. My mail address is [email protected].

My dream in writing this book will be successful if the students are benefited from this book.

SHYAMALENDU KANDAR