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

  1. GRAMMARS AND NATURAL LANGUAGE PROCESSING
  2. GRAMMARS AND LANGUAGES GENERATED
  3. GRAMMARS AND LANGUAGES GENERATED (Contd)
  4. AMBIGUITY IN CFG
  5. SIMPLICATION OF CFG
  6. REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG
  7. GREIBACH NORMAL FORM FOR CFG
  8. FINAL STATE AUTOMATA
  9. NON DETERMINISTIC FSA
  10. NON DETERMINISTIC FSA (Contd)
  11. NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES
  12. EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS
  13. REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA
  14. DFSA TO REGULAR EXPRESSIONS
  15. PROBLEMS AND SOLUTIONS-I
  16. PUMPING LEMMAS FOR REGULAR SETS AND CFL
  17. MYHILL - NERODE THEOREM
  18. MINIMIZATION OF DFSA
  19. FSA WITH OUTPUT MOORE AND MEALY MACHINES
  20. PUSHDOWN AUTOMATA
  21. PUSHDOWN AUTOMATA , EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE AND ACCEPTANCE BY FINAL STATE
  22. PUSHDOWN AUTOMATA CFG TO PDA
  23. PUSHDOWN AUTOMATA PDA TO CFG
  24. PROBLEMS AND SOLUTIONS-II
  25. PROBLEMS AND SOLUTIONS - III
  26. TURING MACHINES
  27. TURING MACHINES (Contd)
  28. TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION
  29. GENERALIZED VERSIONS OF TURING MACHINES
  30. TURING MACHINE AS A GENERATING DEVICE
  31. RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM
  32. PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY
  33. RICE'S THEOREM , LINEAR BOUNDED AUTOMATA , PROPERTIES OF TM
  34. POST'S CORRESPONDENCE PROBLEMS
  35. POST'S CORRESPONDENCE PROBLEMS (Contd), TIME AND TAPE COMPLEXITY OT TM
  36. NP - COMPLETE PROBLEMS , COOK'S THEOREM
  37. NP - COMPLETE PROBLEMS (Contd)
  38. REGULATED REWRITING
  39. L - SYSTEMS
  40. GRAMMAR SYSTEMS
  41. DNA COMPUTING
  42. 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