Theory Of Computation

The aim of this book is to bring light to the computational phenomena. The traditional vehicle for studying computation in general is to introduce a model and then generalize. Chapter 1 deals with various mathematical preliminaries that include the concept of graphs trees sets relations strings abstract languages and mathematical induction. It also incorporates regular languages finite state automata its types proofs theorems and lemma with sufficient number of solved problems with a syntactically simple language. Chapter 2 and 3 deals with formal grammar hierarchy of grammars context free grammar pushdown automata and properties of context free languages. Chapter 4 illustrates about Turing machine and more emphasis on their role as a general model of computation. Chapter 5 focuses on undecidability and more stress has been placed on polynomial-time decidability the sets P NP and NP completeness including computable functions with adequate examples. The key feature of this book is that the proofs are formal and explicit the notations and formatting are mentioned clearly in an understandable way. It consists of ample examples to enable absolute understanding of the basic concepts. Besides these the book also comprises of chapter-end review questions.