Preface – Introduction to Automata Theory, Formal Languages and Computation


What, How and Why—these three words are related to education. ‘What’ only fulfills the basic knowledge, ‘How’ is related to engineering and ‘Why’ makes the knowledge complete.

Bachelors of Computer Science and Engineering has to not only learn some application software and some programming languages but also they must learn how a programming language works, how a program is compiled, how input is converted to output from the machine hardware level. 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 Bachelors of Technology of Computer Science or Information Technology under any university.

Automata theory lies on digital electronics and extends to algorithm and computational complexity. It is the base of compiler design. So, the knowledge of automata theory is very important for graduate and post-graduate students of computer science or information technology.

During my teaching career I have seen that students are frightened of this subject and have realized that they need a book with detailed discussion on few topics presented lucidly. They want more numbers of solved problems where solving is done step by step. Now-a-days multiple choice questions are essential as in different university question papers and competitive exams, these types of questions come. Keeping all this in mind, this book is framed. It contains more than 450 solved problems which include question papers from UPTU, WBUT, JNTU, Pune University, Gujarat Technical University, etc. With each chapter a number of MCQ and fill in the blanks are added. One of the important features of the book is that it contains 20 years’ (1992–2012) GATE solved questions on automata theory. This will help the students a lot in preparing for GATE, NET, etc. In addition, each chapter contains exercises for practice. The difficult questions have clues to solve.

The book contains 14 chapters which covers preliminaries, grammar and languages, finite automata, finite state machine, regular expression, context-free grammar, push down automata, Turing machine, variations of Turing machine, undecidability, recursive function, computational complexity, basics of compiler design and some advance topics related to automata. The Index will help to easily search any topic included in the book.

The book is written mainly according to the syllabus of major technical universities like Jadavpur University, ISM, BESU, WBUT, UPTU, Andhra University, JNTU, Pune University, Gujarat Technical University and different NITs like NIT Durgapur, NIT Rourchella, NIT, Trichi, NIT, Shilchar, etc.

The readers are welcomed to send suggestions, advice for further improvement of the book. The mail address is

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


Shyamalendu Kandar