# Theory of Automata, Formal Languages and Computation

- Institution: IIT Madras
- Department: Computer Science and Engineering
- Teacher: Prof. Kamala Krithivasan
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106106049)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106106049)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [GRAMMARS AND NATURAL LANGUAGE PROCESSING](https://invisiblenetwork.ai/learn/nptel/106106049/42ff068be30a) (Video)
2. [GRAMMARS AND LANGUAGES GENERATED](https://invisiblenetwork.ai/learn/nptel/106106049/80ebfd007ad7) (Video)
3. [GRAMMARS AND LANGUAGES GENERATED (Contd)](https://invisiblenetwork.ai/learn/nptel/106106049/e1fca9255b8f) (Video)
4. [AMBIGUITY IN CFG](https://invisiblenetwork.ai/learn/nptel/106106049/c4bc3dde0455) (Video)
5. [SIMPLICATION OF CFG](https://invisiblenetwork.ai/learn/nptel/106106049/290abdad7734) (Video)
6. [REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG](https://invisiblenetwork.ai/learn/nptel/106106049/d9e8f2f59db7) (Video)
7. [GREIBACH NORMAL FORM FOR CFG](https://invisiblenetwork.ai/learn/nptel/106106049/d7792887a921) (Video)
8. [FINAL STATE AUTOMATA](https://invisiblenetwork.ai/learn/nptel/106106049/a6ce5ad46956) (Video)
9. [NON DETERMINISTIC FSA](https://invisiblenetwork.ai/learn/nptel/106106049/5a2b708cbb9c) (Video)
10. [NON DETERMINISTIC FSA (Contd)](https://invisiblenetwork.ai/learn/nptel/106106049/8c08b6e2af17) (Video)
11. [NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES](https://invisiblenetwork.ai/learn/nptel/106106049/e8e76a123141) (Video)
12. [EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS](https://invisiblenetwork.ai/learn/nptel/106106049/8bc935cea2a1) (Video)
13. [REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA](https://invisiblenetwork.ai/learn/nptel/106106049/997eb92bc19c) (Video)
14. [DFSA TO REGULAR EXPRESSIONS](https://invisiblenetwork.ai/learn/nptel/106106049/569611471cac) (Video)
15. [PROBLEMS AND SOLUTIONS-I](https://invisiblenetwork.ai/learn/nptel/106106049/61d537c6291a) (Video)
16. [PUMPING LEMMAS FOR REGULAR SETS AND CFL](https://invisiblenetwork.ai/learn/nptel/106106049/35fd9af15898) (Video)
17. [MYHILL - NERODE THEOREM](https://invisiblenetwork.ai/learn/nptel/106106049/91767e5cfa4e) (Video)
18. [MINIMIZATION OF DFSA](https://invisiblenetwork.ai/learn/nptel/106106049/105eedc03a60) (Video)
19. [FSA WITH OUTPUT MOORE AND MEALY MACHINES](https://invisiblenetwork.ai/learn/nptel/106106049/5ef9d6aefe12) (Video)
20. [PUSHDOWN AUTOMATA](https://invisiblenetwork.ai/learn/nptel/106106049/1d143c6f36e8) (Video)
21. [PUSHDOWN AUTOMATA , EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE AND ACCEPTANCE BY FINAL STATE](https://invisiblenetwork.ai/learn/nptel/106106049/5d8cdc6973e4) (Video)
22. [PUSHDOWN AUTOMATA CFG TO PDA](https://invisiblenetwork.ai/learn/nptel/106106049/eb0230fe2ef2) (Video)
23. [PUSHDOWN AUTOMATA PDA TO CFG](https://invisiblenetwork.ai/learn/nptel/106106049/7c10b9368298) (Video)
24. [PROBLEMS AND SOLUTIONS-II](https://invisiblenetwork.ai/learn/nptel/106106049/803d7a024b06) (Video)
25. [PROBLEMS AND SOLUTIONS - III](https://invisiblenetwork.ai/learn/nptel/106106049/c002dc14b3fb) (Video)
26. [TURING MACHINES](https://invisiblenetwork.ai/learn/nptel/106106049/36a37e780943) (Video)
27. [TURING MACHINES (Contd)](https://invisiblenetwork.ai/learn/nptel/106106049/17bf93610271) (Video)
28. [TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION](https://invisiblenetwork.ai/learn/nptel/106106049/f47ad286dfb3) (Video)
29. [GENERALIZED VERSIONS OF TURING MACHINES](https://invisiblenetwork.ai/learn/nptel/106106049/c45d3efabf4d) (Video)
30. [TURING MACHINE AS A GENERATING DEVICE](https://invisiblenetwork.ai/learn/nptel/106106049/2c279f07e202) (Video)
31. [RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM](https://invisiblenetwork.ai/learn/nptel/106106049/4af1d2ed44cf) (Video)
32. [PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY](https://invisiblenetwork.ai/learn/nptel/106106049/fe043787789d) (Video)
33. [RICE'S THEOREM , LINEAR BOUNDED AUTOMATA , PROPERTIES OF TM](https://invisiblenetwork.ai/learn/nptel/106106049/0f16125ada21) (Video)
34. [POST'S CORRESPONDENCE PROBLEMS](https://invisiblenetwork.ai/learn/nptel/106106049/302a363f68db) (Video)
35. [POST'S CORRESPONDENCE PROBLEMS (Contd), TIME AND TAPE COMPLEXITY OT TM](https://invisiblenetwork.ai/learn/nptel/106106049/69859e85ef72) (Video)
36. [NP - COMPLETE PROBLEMS , COOK'S THEOREM](https://invisiblenetwork.ai/learn/nptel/106106049/09071dea56df) (Video)
37. [NP - COMPLETE PROBLEMS (Contd)](https://invisiblenetwork.ai/learn/nptel/106106049/fb893bf2c51f) (Video)
38. [REGULATED REWRITING](https://invisiblenetwork.ai/learn/nptel/106106049/f3992bdb9d09) (Video)
39. [L - SYSTEMS](https://invisiblenetwork.ai/learn/nptel/106106049/b67c16947b14) (Video)
40. [GRAMMAR SYSTEMS](https://invisiblenetwork.ai/learn/nptel/106106049/6da2ce2b6fb4) (Video)
41. [DNA COMPUTING](https://invisiblenetwork.ai/learn/nptel/106106049/cd5e66a50181) (Video)
42. [MEMBRANE COMPUTING](https://invisiblenetwork.ai/learn/nptel/106106049/b2c8482826ce) (Video)