Theory of Automata, Formal Languages and Computation
IIT Madras, , Prof. Kamala Krithivasan
Added to favorite list
Updated On 02 Feb, 19
Grammars, Languages generated, Chomskian Hierarchy, CFG, Ambiguity, Reduced grammars, Normal forms - FSA,NFSA, NFSA with moves, Regular expressions, Equivalence of regular expression and FSA, Equivalence of type 3 grammars and FSA, Pumping lemma , Closure and decidability results , Myhill- Nerode theorem, Minimization, FSA with output, Problems - Pushdown Automata, Acceptance by final state and empty store, Equivalence to CFG , Deterministic PDA - Problems and Solutions - Turing Machines - Construction, Techniques of TM construction , TM as acceptor and i/o device , Problems . Generalized and restricted versions - Halting problems - Universal TM-recursive and recursively enumerable sets - Decidability - Rices Theorem , PCP - Time and Tape complexity of TM , P and NP, Cooks theorem - NP-Complete Problems - Advanced topics , Regulated rewritin , L systems Grammar system - New Paradigms of computing , DNA computing , Membrane computing
4.1 ( 11 )
Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit httpnptel.iitm.ac.in
Sep 12, 2018
Excellent course helped me understand topic that i couldn't while attendinfg my college.
March 29, 2019
Great course. Thank you very much.