Theory Of Computation


toc

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

Custom Search

%d bloggers like this: