# Formal Languages and Automata Theory

- Institution: IIT Guwahati
- Department: Mathematics
- Taught by: Dr. K.V. Krishna, Dr. Diganta Goswami
- Level: Undergraduate
- Language: English
- Subjects: Mathematics
- Source: [NPTEL](https://nptel.ac.in/courses/111103016)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/111103016)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [Introduction](https://invisiblenetwork.ai/learn/nptel/111103016/cbf319ef01eb) (Video)
2. [Alphabet, Strings, Languages](https://invisiblenetwork.ai/learn/nptel/111103016/26668c3ef31d) (Video)
3. [Finite Representation](https://invisiblenetwork.ai/learn/nptel/111103016/4c8133561748) (Video)
4. [Grammars (CFG)](https://invisiblenetwork.ai/learn/nptel/111103016/ff3b0757e353) (Video)
5. [Derivation Trees](https://invisiblenetwork.ai/learn/nptel/111103016/30c5d44048af) (Video)
6. [Regular Grammars](https://invisiblenetwork.ai/learn/nptel/111103016/751afe6f2b50) (Video)
7. [Finite Automata](https://invisiblenetwork.ai/learn/nptel/111103016/f08596a7df81) (Video)
8. [Nondeterministic Finite Automata](https://invisiblenetwork.ai/learn/nptel/111103016/5b4d67a78151) (Video)
9. [NFA DFA](https://invisiblenetwork.ai/learn/nptel/111103016/be3c38653af0) (Video)
10. [Myhill-Nerode Theorem](https://invisiblenetwork.ai/learn/nptel/111103016/8cb4bdb28469) (Video)
11. [Minimization](https://invisiblenetwork.ai/learn/nptel/111103016/f36bfcc22dbc) (Video)
12. [RE => FA](https://invisiblenetwork.ai/learn/nptel/111103016/c225dc0425ea) (Video)
13. [FA => RE](https://invisiblenetwork.ai/learn/nptel/111103016/a47c335f6133) (Video)
14. [FA RG](https://invisiblenetwork.ai/learn/nptel/111103016/930ede7bb768) (Video)
15. [Variants of FA](https://invisiblenetwork.ai/learn/nptel/111103016/a5fb40d5924a) (Video)
16. [Closure Properties of RL](https://invisiblenetwork.ai/learn/nptel/111103016/e4093f45603e) (Video)
17. [Homomorphism](https://invisiblenetwork.ai/learn/nptel/111103016/c659353c6362) (Video)
18. [Pumping Lemma](https://invisiblenetwork.ai/learn/nptel/111103016/23e6b9afb223) (Video)
19. [Simplification of CFG](https://invisiblenetwork.ai/learn/nptel/111103016/b7500f1ddc55) (Video)
20. [Normal Forms of CFG](https://invisiblenetwork.ai/learn/nptel/111103016/7524368af207) (Video)
21. [Properties of CFLs](https://invisiblenetwork.ai/learn/nptel/111103016/a09bc46ef277) (Video)
22. [Pushdown Automata](https://invisiblenetwork.ai/learn/nptel/111103016/1cabb32c3264) (Video)
23. [PDA CFG](https://invisiblenetwork.ai/learn/nptel/111103016/cf7f68f77e91) (Video)
24. [Turing Machines](https://invisiblenetwork.ai/learn/nptel/111103016/1001d33e43d1) (Video)
25. [Turing Computable Functions](https://invisiblenetwork.ai/learn/nptel/111103016/72600fa822f3) (Video)
26. [Combining Turing Machines](https://invisiblenetwork.ai/learn/nptel/111103016/99492bc759fa) (Video)
27. [Multi Input](https://invisiblenetwork.ai/learn/nptel/111103016/5b476e9e7ad5) (Video)
28. [Turing Decidable Languages](https://invisiblenetwork.ai/learn/nptel/111103016/3964ecbf4b6d) (Video)
29. [Varients of Turing Machines](https://invisiblenetwork.ai/learn/nptel/111103016/fc0598440c60) (Video)
30. [Structured Grammars](https://invisiblenetwork.ai/learn/nptel/111103016/a3ccf7017a09) (Video)
31. [Decidability](https://invisiblenetwork.ai/learn/nptel/111103016/72c3c6aa0420) (Video)
32. [Undecidability1](https://invisiblenetwork.ai/learn/nptel/111103016/3f7168513b4a) (Video)
33. [Undecidability2](https://invisiblenetwork.ai/learn/nptel/111103016/48d92b73b1bd) (Video)
34. [Undecidability3](https://invisiblenetwork.ai/learn/nptel/111103016/2898c5b8d918) (Video)
35. [Time Bounded Turing Machines](https://invisiblenetwork.ai/learn/nptel/111103016/7f7ca2fccd25) (Video)
36. [P and NP](https://invisiblenetwork.ai/learn/nptel/111103016/bcfb95b367bf) (Video)
37. [NP-Completeness](https://invisiblenetwork.ai/learn/nptel/111103016/29e3842d344c) (Video)
38. [NP-Complete Problems1](https://invisiblenetwork.ai/learn/nptel/111103016/2933bb93dc17) (Video)
39. [NP-Complete Problems2](https://invisiblenetwork.ai/learn/nptel/111103016/43afa8d50b94) (Video)
40. [NP-Complete Problems3](https://invisiblenetwork.ai/learn/nptel/111103016/a3d114f28cde) (Video)
41. [Chomsky Hierarchy](https://invisiblenetwork.ai/learn/nptel/111103016/f23655cf192f) (Video)