Theory of Automata, Formal Languages and Computation

IIT Madras Course , Prof. Kamala Krithivasan

588 students enrolled

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

Lecture 1: GRAMMARS AND NATURAL LANGUAGE PROCESSING

Up Next
You can skip ad in
SKIP AD >
Advertisement
      • 2x
      • 1.5x
      • 1x
      • 0.5x
      • 0.25x
        EMBED LINK
        COPY
        DIRECT LINK
        PRIVATE CONTENT
        OK
        Enter password to view
        Please enter valid password!
        0:00
        3.7 (3 Ratings)

        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

        LECTURES



        Review


        3.7

        3 Rates
        4
        67%
        2
        3
        33%
        1

        Comments Added Successfully!
        Please Enter Comments
        Please Enter CAPTCHA
        Invalid CAPTCHA
        Please Login and Submit Your Comment

        LECTURES