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.
This note exlains the following topics: foundational concepts
like strings and DFAs, then progresses to regular expressions, nondeterministic
automata, and formal language theory, Advanced topics include Turing machines,
decidability, and language-related problems it offers a comprehensive look at
formal languages, automata, and computability.
This PDF covers the
following topics related to Theory of Computation : Mechanical Computation,
Background, Languages and graphs, Automata, Computational Complexity.
This note covers the following topics: Sets,
functions and other preliminaries, Formal Languages, Finite Automata ,
Regular Expressions, Turing Machines, Context-Free Languages, Rice's Theorem,
Time complexity, NP-Completeness, Space Complexity , Log Space, Oracle
machines and Turing Reducibility, Probabilistic Complexity, Approximation and
Optimisation, Complexity Hierarchy Theorems.
This note provides
an introduction to the theory of computational complexity. Topics covered
includes: Models of computation, Time and space complexity classes,
Nonterminism and NP, Diagonalization, Oracles and relativization, Alternation,
Space complexity, Natural proofs, Randomized classes, Counting classes,
Descriptive complexity and Interactive proofs.
This is a free textbook for an undergraduate course
on the Theory of Computation, which have been teaching at Carleton University
since 2002.Topics covered includes: Finite Automata and Regular Languages,
Context-Free Languages, Turing Machines and the Church-Turing Thesis,
Decidable and Undecidable Languages and Complexity Theory.
This book covers the
following topics: The RAM Model, The Primitive Recursive Functions, The
Partial Recursive Functions, Coding and Godelization, The Hierarchy of
Primitive Recursive Functions, Universality and Parametrisation, The type-free
lambda calculus.
This note covers the following topics: A brief history of
computing, Fundamentals, Formal languages and machine models, Computability
and undecidability, NP-completeness, Generalized number systems and
Cryptography mental poker.
This note covers the following
topics: introduction to theoretical computer science, language, regular
language, finite automata, language accepted by dfa, nondeterministic finite
automata, equivalence of nfa, regular language and fa, application of fa,
nonregular languages, context free languages, turing machines, computability
and complexity.
Author(s): Pavan
Kumar Anumula, Andrea Di Fabio and Jia Zhu
This is an executable course note
implemented in Pidgin ML, which is a core subset of the Objective Caml
programming language under the so-called revised syntax.