Models of Computation by John E. Savage
This book, written for graduates, covers general subjects on computational models, logic circuits, and memory machines, with advanced subjects being parallel computation, circuit complexity, and space-time trade-offs; therefore, it's a very thorough course on computational models and their complexities.
Author(s): John E. Savage, Brown University
698 Pages 
Theory of Computation by Frank Stephan
Frank Stephan's detailed lecture notes on the theory of computation cover quite a wide spectrum of issues. The document starts with the basics of sets and regular expressions, then goes ahead to grammars and the Chomsky hierarchy, helping one in understanding the structure of languages. Then it discusses finite automaton and nondeterministic finite automata, giving all details about the processing of strings by these models. The notes also treat the composition of languages, normal forms, and algorithms used in computation. Membership testing, whether deterministic or nondeterministic, is also explained, together with the proof of how models of computation handle language recognition. Finally, the approach is important when considering complexity, the problems that turn out undecidable, showing thus the intrinsic limits of computation. This is an important resource concerning formal languages, automata theory, and basic bounds of computability.
Author(s): Frank Stephan
176 Pages
Introduction to the Theory of Computation Lecture Notes
These are lecture notes from the University of Toronto, giving a very brief introduction to some of the basic ideas in the theory of computation. We start with some basic topics: induction and recursion; the correctness of programs, that must be understood if more advanced computational theories are to be enlightened. Then we go on to develop the topics of regular languages and finite automata, giving the basic models and techniques used in analysing and recognising regular languages. The coverage is designed to provide students with a reasonably solid grounding in the basic ideas of the theory of computation and to render a clear and thorough exposition of the fundamental concepts underlying more advanced topics.
Author(s): University of Toronto
75 Pages
Introduction to the Theory of Computing
Introduction to the Theory of Computing is a course that undertakes an intensive study of the underpinnings of the theory of computation. Beginning with mathematical foundations, the course moves into regular operations and expressions, and then into proofs on languages being nonregular and other further treatments on regular languages. Other important topics include parse trees, ambiguity, Chomsky normal form, pushdown automata, and Turing machines. Further, the PDF discusses various types of Turing machines, the stack machine model, and undecidable languages, making it a great starting point in the topic of computability.
Author(s): University of Waterloo
227 Pages
Theory of Computation by Kyle Burke
This book surveys some of the most relevant theoretical concepts with computational models. The limits of computation, undecidability of the Halting Problem, several automata models, including both deterministic and nondeterministic finite-state automata, pushdown automata, and Turing machines, are introduced. The ending is dedicated to computational complexity, with NP-Completeness, approximation algorithms, and hardness of approximation.
Author(s): Kyle Burke
114 Pages
Models of Computation by John E. Savage
This book, written for graduates, covers general subjects on computational models, logic circuits, and memory machines, with advanced subjects being parallel computation, circuit complexity, and space-time trade-offs; therefore, it's a very thorough course on computational models and their complexities.
Author(s): John E. Savage, Brown University
698 Pages
Introduction to Computational Theory Lecture Notes
These broad-ranging notes introduce some of the fundamental concepts in the theory of computation. The set starts with a brief introduction to formal languages and their classification, including regular languages and sets. In these notes, finite automata are introduced, discussing their structure and role in recognizing regular languages. This is followed by Context-Free Grammars and Pushdown Automata, focusing on the role in defining and recognizing context-free languages. This will cover Turing Machines, the original model of computation; a review of the Chomsky Hierarchy from a perspective on the various levels of languages about their power of generation. The conclusion deals with an overview of Complexity Theory, mainly dealing with the P and NP problems. It gives insight into the computational complexity in general and into the famous P vs NP questions.
Author(s): BYU Computer Science Department
NA Pages
