Email: Incstuart@gmail.com

Stuart
TOC
January 13, 2018

### Theory Of Computation

FINITE AUTOMATA
Introduction: Basic Mathematical Notation and techniques
Finite State systems, Basic Definitions, Finite Automaton : DFA
Finite Automaton : NDFA, Finite Automaton with €- moves
Regular Languages- Regular Expression
Equivalence of NFA and DFA
Equivalence of NDFA’s with and without €-moves
Equivalence of finite Automaton and regular expressions
Minimization of DFA
Pumping Lemma for Regular sets, Problems based on Pumping Lemma
GRAMMARS
Grammar Introduction: Types of Grammar, Context Free Grammars and
Languages
Derivations, Ambiguity, Relationship between derivation and derivation
trees
Simplification of CFG: Elimination of Useless Symbols
Simplification of CFG: Unit productions , Null productions
Chomsky normal form
Problems related to CNF
Greiback Normal form
Problems related to GNF
PUSHDOWN AUTOMATA
Pushdown Automata: Definitions Moves, Instantaneous descriptions
Deterministic pushdown automata
Problems related to DPDA
Non - Deterministic pushdown automata
Equivalence : Pushdown automata to CFL
Equivalence : CFL to Pushdown automata
Problems related to PDA to CFG and CFG to PDA
Pumping lemma for CFL, Problems based on pumping Lemma
TURING MACHINE
Turing Machines: Introduction, Formal definition of Turing machines,
Instantaneous descriptions
Turing Machine as Acceptors
Problems related to Turing Machine as Acceptors
Turing Machine for computing functions( Transducer)
Turing Machine constructions
Modifications of Turing Machines
COMPUTATIONAL COMPLEXITY
Undecidability :Basic definitions, Decidable problems
Examples of undecidable problems
Rice’s Theorem
Undecidable problems about Turing Machine – Post’s Correspondence
Problem
Properties of Recursive and Recursively enumerable languages
Introduction to Computational Complexity: Definitions, Time and Space
complexity of TMs
Complexity classes: Class P, Class NP
Complexity classes: Introduction to NP-Hardness and NP-Completeness
### Share:

*Popular on Stuartown*

%d bloggers like this: