Learn · NPTEL

Course10610604942 lectures

Theory of Automata, Formal Languages and Computation

Prof. Kamala Krithivasan · IIT Madras

Start with lecture 1 At NPTEL

Lectures

Grammars: Properties of Context Free Grammars

  1. GRAMMARS AND NATURAL LANGUAGE PROCESSING Video
  2. GRAMMARS AND LANGUAGES GENERATED Video
  3. GRAMMARS AND LANGUAGES GENERATED (Contd) Video
  4. AMBIGUITY IN CFG Video
  5. SIMPLICATION OF CFG Video
  6. REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG Video
  7. GREIBACH NORMAL FORM FOR CFG Video

Finite State Automata and Regular Expressions

  1. FINAL STATE AUTOMATA Video
  2. NON DETERMINISTIC FSA Video
  3. NON DETERMINISTIC FSA (Contd) Video
  4. NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES Video
  5. EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS Video
  6. REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA Video
  7. DFSA TO REGULAR EXPRESSIONS Video
  8. PROBLEMS AND SOLUTIONS-I Video
  9. PUMPING LEMMAS FOR REGULAR SETS AND CFL Video
  10. MYHILL - NERODE THEOREM Video
  11. MINIMIZATION OF DFSA Video
  12. FSA WITH OUTPUT MOORE AND MEALY MACHINES Video

Pushdown Automata

  1. PUSHDOWN AUTOMATA Video
  2. PUSHDOWN AUTOMATA , EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE AND ACCEPTANCE BY FINAL STATE Video
  3. PUSHDOWN AUTOMATA CFG TO PDA Video
  4. PUSHDOWN AUTOMATA PDA TO CFG Video

Problems and Solutions

  1. PROBLEMS AND SOLUTIONS-II Video
  2. PROBLEMS AND SOLUTIONS - III Video

Turing Machines

  1. TURING MACHINES Video
  2. TURING MACHINES (Contd) Video
  3. TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION Video
  4. GENERALIZED VERSIONS OF TURING MACHINES Video
  5. TURING MACHINE AS A GENERATING DEVICE Video

Decidability

  1. RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM Video
  2. PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY Video
  3. RICE'S THEOREM , LINEAR BOUNDED AUTOMATA , PROPERTIES OF TM Video
  4. POST'S CORRESPONDENCE PROBLEMS Video

Introduction to Complexity Theory

  1. POST'S CORRESPONDENCE PROBLEMS (Contd), TIME AND TAPE COMPLEXITY OT TM Video
  2. NP - COMPLETE PROBLEMS , COOK'S THEOREM Video
  3. NP - COMPLETE PROBLEMS (Contd) Video

Advanced Topics

  1. REGULATED REWRITING Video
  2. L - SYSTEMS Video
  3. GRAMMAR SYSTEMS Video

New Paradigms of Computing

  1. DNA COMPUTING Video
  2. MEMBRANE COMPUTING Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Madras
Department
Computer Science and Engineering
Teacher
Prof. Kamala Krithivasan
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed