Asia Pacific University Library catalogue

The book contains in-depth coverage of all the topics related to the theory of computation as mentioned in the syllabuses of B.E., M.C.A., and M.Sc. (Computer Science) of various universities. A sufficient amount of theoretical inputs supported by a number of illustrations are included for those who take a deep interest in the subject. In the first few chapters, the book presents the necessary basic material for the study of automata theories. Examples of topics included are regular languages and Kleene's Theorem; minimal automata and syntactic monoids; the relationship between context-free languages and pushdown automata; and Turing machines and decidability. This book facilitates students a more informal writing style while providing the most accessible coverage of automata theory, solid treatment on constructing proofs, many figures and diagrams to help convey ideas, and sidebars to highlight related material. Each chapter offers an abundance of exercises for hands-on learning. Expressing everything clearly, concisely and correctly requires a certain degree of formalization. I assume basic knowledge of discrete mathematics, only. In particular, it may be helpful if the reader has a basic understanding of what constitutes proof of a mathematical assertion. All the remaining material is introduced in the text. Fundamental concepts are exemplified, too. I am strongly convinced that a solid compromise between formal correctness and intuitive ideas may help both the students and instructors to enjoy the wealth of insight this book is aiming to present. The main emphasis is put on the interaction of theory and practice in informatics. Theory must deal with problems of practical importance and practical informatics needs a solid foundation to develop its full potential. Therefore, two thirds of the book are devoted to formal languages and automata theory. Formal languages are indispensable for applied computer science since one meets them everywhere. Thus, i cover grammars (formalizing the generation), automata (formalizing the acceptance) and their interaction for regular and context-free languages.