Please enable JavaScript.
Coggle requires JavaScript to display documents.
COMPUTATION, Neso academy - Theory of computation & automata theory…
COMPUTATION
Neso academy - Theory of computation & automata theory
Introduction to theory of computation
Finite state machine (prerequisite)
Finite state machine (finite automata)
Deterministic finite automata (4 examples)
Regular languages
Operations on regular languages
Non-deterministic finite automata
Formal definition of non-deterministic finite automata (NFA)
Non-deterministic finite automata (3examples)
Conversion of NFA to DFA
20 Minimization of deterministic finite automata (DFA)
Minimization of DFA
Minimization of DFA (with multiple final states)
Myhill nerode theorem - table filling method
Finite automata with outputs
Construction of mealy machine
Construction of Moore machine
Conversion of moore machine to mealy machine
Conversion of mealy machine to moore machine
Conversion of mealy machine to moore machine (using transition table)
Epsilon NFA
Conversion of epsilon NFA to NFA
Regular expression
Regular expression - examples
Identities of regular expression
Arden's theorem
An example proof using identities of regular expressions
Designing regular expressions
NFA to Regular expression Conversion
DFA to Regular expression conversion
DFA to regular expression conversion
Conversion of regular expression to finite automata
Equivalence of two finite automata
Pumping lemma (for regular languages)
Regular grammar
Derivations from a grammar
Context free grammar & context free language
Regular languages & finite automata
Methods to find whether a string belong to a grammar or not
Derivation tree (left & right derivation trees)
Ambiguous grammar
Simplification of CFG (Reduction of CFG)
Simplification of CFG (Removal of unit productions)
Simplification of CFG (Removal of Null Productions)
Chomsky normal form % CFG to CNF conversion
Conversion of CFG to Chomsky normal form
Greivach normal form & CFG to GNF conversion
CFG to GNF conversion (Remove of left recursion)
Pumping lemma (For context free languages)
Pushdown automata (introduction)
Pushdown automata (formal definition)
Pushdown automata (Graphic notation)
Pushdown automata example
Equivalence of CFG and PDA
Turing machine - Introduction
Turing machines (Formal definition)
Turing machine (examples)
The church-turing thesis
Turing machine for even palindromes
Turing machine programming techniques
Multitape turing machine
Nondeterministic turing machines
Turing machine as problem solvers
Decidability and undecidability
Universal turing machines
The Halting problem
Undecidability of the halting problem
The post correspondence problem
Undecidability of the post correspondance problem
TOC - conclusion and summary
Tom Stuart - Understanding Computation
Just enough Ruby
The meaning of programs
The simplest computers
Just add power
The ultimate machine
Programming with nothing
Universality is everywhere
Impossible programs
Programming in Toyland
Michael sipser - Introduction to the theory of computation
Introduction
0.1 Automata, Computability, and Complexity
0.2. Mathematical notions and terminology
Definitions, Theorems, and Proofs
0.4. Types of proof
Part One: Automata and languages
Regular languages
Context-free languages
Part two: Computability theory
The church-turing thesis
Decidability
Reducidability
Advanced topics in Computablity theory
Part Three: Complexity theory
Time-Complexity
Space complexity
Intractability
Advanced topics in complexity theory