Introduction to Theory of Computation by Wikiversity
This is an all-inclusive course on computational theory provided in this online resource by Wikiversity. It begins with Finite State Machines–their definitions, operations, and minimization techniques. The notes also cover closure and nondeterminism—how these properties may affect computational models. Their discussion greatly involves the Pumping Lemma, proving language property. The book also surveys Context-Free Languages and their connection to Compilers and introduces Pushdown Machines emphatically and focuses on their importance in parsing. It contains important material on the CYK algorithm for parsing and the more basic problems of Undecidability. It also surveys Turing Machines, the Halting Problem, and more general areas of Complexity Theory, including Quantified Boolean Formulae, Savitch's Theorem, and Space Hierarchy. The notes end with the Recursion Theorem, and it can be considered as a landmark in the theoretical study of the science of computers.
Author(s): Wikiversity
NA 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
Lecture Notes of Introduction to the Theory of Computation
Authored by Margaret Fleck and Sariel Har Peled, this is a wide set of lecture notes on the theory of computation. These start with the very basic objects such as strings and deterministic finite automata (DFAs) before moving up to regular expressions and nondeterministic automata. This course covers formal language theory, including some advanced topics such as Turing machines, decidability, and several language-related problems. It is intended that these notes afford a comprehensively broad yet deep exploration of the formal languages, automata, and computability material with an excellent bibliography that creates interest among students and researchers.
Author(s): Margaret Fleck and Sariel Har Peled
345 Pages
Introduction to Theory of Computation by Wikiversity
This is an all-inclusive course on computational theory provided in this online resource by Wikiversity. It begins with Finite State Machines–their definitions, operations, and minimization techniques. The notes also cover closure and nondeterminism—how these properties may affect computational models. Their discussion greatly involves the Pumping Lemma, proving language property. The book also surveys Context-Free Languages and their connection to Compilers and introduces Pushdown Machines emphatically and focuses on their importance in parsing. It contains important material on the CYK algorithm for parsing and the more basic problems of Undecidability. It also surveys Turing Machines, the Halting Problem, and more general areas of Complexity Theory, including Quantified Boolean Formulae, Savitch's Theorem, and Space Hierarchy. The notes end with the Recursion Theorem, and it can be considered as a landmark in the theoretical study of the science of computers.
Author(s): Wikiversity
NA 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
Introduction to Theory of Computation Lecture Notes
These lecture notes give an introduction to the more fundamental parts of the theory of computation and begin by presenting finite automata: starting with deterministic and nondeterministic finite automata, their equivalence, and practical implications of these concepts. The lecture notes include sections on regular expressions and their relationship to finite automata, non-regular languages, and the Pumping Lemma to prove non-regularity. Myhill-Nerode Theorem: For understanding recognition of languages. The notes go further to present context-free languages, including their ambiguity and properties of closure. The pumping lemma for context-free languages is also discussed, while decidable and recognizable languages are informed by a deep underpinning in computational theory.
Author(s): Mahesh Viswanathan
NA Pages
Advanced Theory in Computation
This is an advanced set of notes on the analysis of algorithms and their complexity. Of interest in these notes are the topics on string matching algorithms, such as Knuth-Morris-Pratt and Boyer-Moore. Suffix trees and dictionary techniques are also part of the discussion here. Among the methods to be shown in a way of analyzing algorithm efficiency are amortized analysis and randomized algorithms. It also treats the pairing technique, Ziv-Lempel coding; further topics on statistical adversaries, portfolio selection, and reservation-price policies that are objects of other techniques discussed herein.
Author(s): Seoul National University
NA Pages
