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 
This note contains below topics, Strings and formal languages, Deterministic and nondeterministic finite automata, Regular expressions, Context free languages, Turing machines, Undecidability.
Author(s): Jeff Erickson, University of Illinois Urbana-Champaign
155 Pages
Introduction to the Theory of Computing
This pdf includes overview and mathematical foundations, Regular operations and regular expressions, Proving languages to be nonregular, Further discussion of regular languages, Parse trees, ambiguity, and Chomsky normal form, Pushdown automata, Turing machines, Variants of Turing machines, Stack machines, Universal Turing machines and undecidable languages, Further discussion of computability.
Author(s): University of Waterloo
227 Pages
Models of Computation by John E Savage
This PDF Models of Computation by John E. Savage covers the following topics related to Computation Theory, The Role of Theory in Computer Science, General Computational Models, Logic Circuits, Machines with Memory, FiniteState Machines and Pushdown Automata, Computability, Algebraic and Combinatorial Circuits, Parallel Computation, Computational Complexity, Complexity Classes, Circuit Complexity, SpaceTime Tradeoffs, MemoryHierarchy Tradeoffs, VLSI Models of Computation.
Author(s): John E. Savage, Brown University
698 Pages
Lecture Notes Theory of Computation
This lecture note from S R Engineering College offers a detailed introduction to key concepts in the Theory of Computation. It begins with Properties of Binary Operations, exploring fundamental mathematical operations and their essential properties like associativity and commutativity. The section on Concatenation Properties covers how strings can be joined and the characteristics of such operations, including associativity and the identity element. Finite Automata are thoroughly discussed, explaining both deterministic and nondeterministic NFA models, and their role in recognizing regular languages. The notes also cover Formal Languages, categorizing them into regular, contextfree, contextsensitive, and recursively enumerable types based on complexity. Finally, the Pumping Lemma is introduced as a critical tool for proving the nonregularity and noncontextfreeness of languages by demonstrating how strings in these languages can be decomposed and manipulated.
Author(s): S R Engineering College
155 Pages
Introduction to Computational Theory Lecture Notes
This note covers the following topics, Languages, Finite Automata, Regular Languages and Sets, ContextFree Grammars, Pushdown Automata and ContextFree Languages, Turing Machines, The Chomsky Hierarchy, P and NP.
Author(s): BYU Computer Science Department
NA Pages
Theory of Computation Tutorials
This set of tutorials goes into the heart of the theory of computer science with formal languages and automatons, computability, and complexity. Topics to be discussed are regular and contextfree languages, finite automata, and pushdown automata. Consequently, resulting tutorials treat topics like Turing machines, Churchs thesis, and the problem of undecidability, whose examples include the and quot,halting problem and quot, in the exploration of the limits of computability. They look into complexity classes such as P, NP, and PSPACE, look into NPcompleteness, or provide an indepth treatment along with a wide introduction to the theoretical foundations of computer science.
Author(s): The Australian National University, Canberra
NA Pages
