x
Menu

Theory of Automata, Formal Languages and Computation

IIT Madras, , Prof. Kamala Krithivasan

Overview

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

Includes

Lecture 1: GRAMMARS AND NATURAL LANGUAGE PROCESSING

4.1 ( 11 )


Lecture Details

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

Ratings

3.7


3 Ratings
55%
30%
10%
3%
2%
Comments
comment person image

Sam

Excellent course helped me understand topic that i couldn't while attendinfg my college.

Reply
comment person image

Dembe

Great course. Thank you very much.

Reply
Send