Theory of Automata, Languages & Computation

This book is specially designed to suit the requisites of various levels of students studying this subject. It endeavours to provide an excellent and user-friendly presentation of the concepts, essential for an introductory course on automata and computation. The text includes the straightforward explanation of complicated ideas like transition functions, two-way FA, equivalence of two automata, equivalence of two regular expressions, pumping lemma, auxiliary and two-stack PDA, equivalence of two-stack PDAs and Turing machines, PDA for regular and context free languages, and Turing machines for regular and non-regular languages. This book explains how a reader can define the transition function if he/she knows the functioning of an automaton and vice-versa in a very easy way. Every concept is followed by examples. The text is illustrated with diagrams. Most of the exercise questions are accompanied with hints, making it easy for the student to solve the problems. In several sections of this book, there are Did You Know and Good to Know boxes that contain interesting information about the major contributors in this field. This is an attractive feature which adds flavour to the text and acts as mental relaxation while reading serious stuff. It keeps the reader’s knowledge updated with some remarkable facts that are hard to find in any textbook on this subject as such. Salient Features • Detailed coverage of important topics such as Finite Automata, Pushdown Automata, Context-Free and Regular Languages. • Exhaustive yet simple and lucid explanation of concepts • Good balance between theoretical and mathematical rigor • Hints and solutions to review exercises, graded problems and multiple-choice questions • ‘Good to Know’ and ‘Did You Know’ features provide additional information and facts about the subject and its history • Excellent pedagogy includes - Over 140 Solved Examples - Over 175 Review Questions - Over 100 Graded Questions - Over 280 Multiple