IIT Madras · Computer Science
Theory of Automata, Formal Languages and Computation
Prof. Kamala Krithivasan · 42 free video lectures
42 video lectures. Topics: GRAMMARS AND NATURAL LANGUAGE PROCESSING; GRAMMARS AND LANGUAGES GENERATED; GRAMMARS AND LANGUAGES GENERATED (Contd); AMBIGUITY IN CFG; SIMPLICATION OF CFG; REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG; GREIBACH NORMAL FORM FOR CFG; FINAL STATE AUTOMATA; NON…
▶ Play on Open Lecture HallCourse page ↗
Lectures
- GRAMMARS AND NATURAL LANGUAGE PROCESSING
- GRAMMARS AND LANGUAGES GENERATED
- GRAMMARS AND LANGUAGES GENERATED (Contd)
- AMBIGUITY IN CFG
- SIMPLICATION OF CFG
- REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG
- GREIBACH NORMAL FORM FOR CFG
- FINAL STATE AUTOMATA
- NON DETERMINISTIC FSA
- NON DETERMINISTIC FSA (Contd)
- NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES
- EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS
- REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA
- DFSA TO REGULAR EXPRESSIONS
- PROBLEMS AND SOLUTIONS-I
- PUMPING LEMMAS FOR REGULAR SETS AND CFL
- MYHILL - NERODE THEOREM
- MINIMIZATION OF DFSA
- FSA WITH OUTPUT MOORE AND MEALY MACHINES
- PUSHDOWN AUTOMATA
- PUSHDOWN AUTOMATA , EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE AND ACCEPTANCE BY FINAL STATE
- PUSHDOWN AUTOMATA CFG TO PDA
- PUSHDOWN AUTOMATA PDA TO CFG
- PROBLEMS AND SOLUTIONS-II
- PROBLEMS AND SOLUTIONS - III
- TURING MACHINES
- TURING MACHINES (Contd)
- TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION
- GENERALIZED VERSIONS OF TURING MACHINES
- TURING MACHINE AS A GENERATING DEVICE
- RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM
- PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY
- RICE'S THEOREM , LINEAR BOUNDED AUTOMATA , PROPERTIES OF TM
- POST'S CORRESPONDENCE PROBLEMS
- POST'S CORRESPONDENCE PROBLEMS (Contd), TIME AND TAPE COMPLEXITY OT TM
- NP - COMPLETE PROBLEMS , COOK'S THEOREM
- NP - COMPLETE PROBLEMS (Contd)
- REGULATED REWRITING
- L - SYSTEMS
- GRAMMAR SYSTEMS
- DNA COMPUTING
- MEMBRANE COMPUTING
From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Madras.
Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights