Theory Of Computation (160704)  


Sr. Topics Teaching Hours Module Weightage
Review Of Mathematical Terms And Theory
Basic Mathematical Notations And Set Theory, Logic Functions And Relations, Language Definitions, Mathematical Inductions And Recursive Definitions
Finite Automata
Deterministic And Non Deterministic Finite Automata, Ù-Transitions, Conversion From NFA To DFA, Kleene’s Theorem, Regular And Non Regular Languages
CFG (Context Free Grammar
Introduction To CFG, CFG And Known Languages, Unions Concatenations And *’S Notations And CFL, Derivations Of Trees And Ambiguity, Unambiguous CFG And Algebric Expressions, Normal Forms And Siplified Forms
Pushdown Automata, CFL and NFL
Introduction To PDA, Definition, DPDA, PDA Corresponding To CFG, CFG Corresponding To PDA, Introduction To CFL, Intersections And Complements Of CFL, Decisions Problems And CFL
Turing Machines, Recursive Language
Model Of Computation And Church Turning Thesis, Definition Of Turing Machine, Tm And Language Acceptors, Variations Of Tm, Non Deterministic Tm, Universal Tm, Enumerable And Language, Recursive And Non Recursive Enumerable
Computation Functions, Measuring, Classifications And Complexity
Primitive Recursive Functions, Halting Problem, Recursive Predicates And Some Bounded Operations, Unbounded Minimizations And µ-Recursive Functions, Godel Numbering, Computable Functions And µ-Recursive, Numerical Functions
Tractable And Intractable Problems
Growth Rate And Functions, Time And Speed Complexity, Complexity Classes, Tractable And Possibly Intractable Problems, P And Np Completeness, Reduction Of Time, Cook’s Theorem, Np-Complete Problems