Theory of Computation by Dr OG Kakde

This book on "Theory of Computation" is written with a view point of giving an exposure to the readers, of the informal understanding of the various concepts, and then their formalization. The organization of the book is such that it first introduces the concept informally, followed by its formalization, immediately followed by it's application in solving the problems. Chapter 1 makes the reader aware of the basic terminologies, and definitions, that are used in the subsequent chapters. Chapters 2 and 3, covers regular expressions, regular languages, and finite automata. Chapter 4 familiarizes with the concept of formal grammar, and hierarchy of grammars. Chapter 5, 6 and 7 cover context free grammar, push down automata, and properties of context free languages. Chapter 8 describes the Turing Machine. Chapter 9 discusses the undecidability, and Chapter 10, gives an overview of recursive function theory. Objective type questions, and two model question papers are also given at the end, along with the answers. Enough number of practice problems are given at the end of every chapter.