IIT Kharagpur · Computer Science

Introduction to Automata, Languages and Computation

Prof. Sourav Mukhopadhyay · 62 free video lectures

62 video lectures. Topics: Deterministic Finite Automata (DFA); Input alphabet; Extended transition function; Language of DFA; Building DFA; Building DFA (contd.); NFA (Nondeterministic Finite Automata); Language of a NFA; Equivalence of DFA's and NFA's; Subset Construction; ϵ-NFA; Extended…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Lecture 1 : Deterministic Finite Automata (DFA)
  2. Lecture 2 : Input alphabet
  3. Lecture 3 : Extended transition function
  4. Lecture 4 : Language of DFA
  5. Lecture 5 : Building DFA
  6. Lecture 06:Building DFA (contd.)
  7. Lecture 07: NFA (Nondeterministic Finite Automata)
  8. Lecture 08: Language of a NFA
  9. Lecture 09: Equivalence of DFA's and NFA's
  10. Lecture 10: Subset Construction
  11. Lecture 11 : ϵ-NFA
  12. Lecture 12 : Extended transition function of 𝜖-NFA
  13. Lecture 13 : Language of 𝜖-NFA
  14. Lecture 14 : 𝜖-NFA to NFA
  15. Lecture 15 : 𝜖-NFA to DFA
  16. Lecture 16 : Regular expression
  17. Lecture 17 : Regular expression (Contd.)
  18. Lecture 18 : More on regular expression
  19. Lecture 19 : Equivalence of 𝜖-NFA and regular expression
  20. Lecture 20 : Equivalence of 𝜖-NFA and regular expression (Contd.)
  21. Lecture 21: DFA to Regular expression
  22. Lecture 22: DFA to Regular expression (Contd.)
  23. Lecture 23: Construction of regular expression from a DFA (example)
  24. Lecture 24: Closure properties of Regular Set
  25. Lecture 25: Closure properties of Regular Set (Contd.)
  26. Lecture 26 : Substitution
  27. Lecture 27 : Pumping Lemma
  28. Lecture 28 : Application of the pumping lemma
  29. Lecture 29 : More on Pumping lemma
  30. Lecture 30 : Arden's Theorem
  31. Lecture 31: Minimization of FA
  32. Lecture 32: Minimization of FA (Cont.)
  33. Lecture 33: Two way FA
  34. Lecture 34: Finite automata with output
  35. Lecture 35: Equivalence of Moore and Mealy machine
  36. Lecture 36: Context free grammars (CFG)
  37. Lecture 37: Context free language (CFL)
  38. Lecture 38: More example on CFL
  39. Lecture 39: More on CFG
  40. Lecture 40: Derivation Tree/Parse Tree
  41. Lecture 41 : Leftmost and Rightmost derivations
  42. Lecture 42 : Ambiguity in CFG
  43. Lecture 43 : Simplification of CFG
  44. Lecture 44 : Algorithms to construct reduced grammar
  45. Lecture 45 : Elimination of Null and Unit productions
  46. Lecture 46 : Chomsky Normal Form (CNF)
  47. Lecture 47 : Greibach Normal Form (GNF)
  48. Lecture 48 : Pushdown Automata (PDA)
  49. Lecture 49 : Language accepted by PDA
  50. Lecture 50 : Example of a language accepted by PDA
  51. Lecture 51 : Deterministic PDA
  52. Lecture 52 : Equivalence of language accepted
  53. Lecture 53 : Equivalence PDA
  54. Lecture 54 : Equivalence PDA and CFL
  55. Lecture 55 : Equivalence PDA and CFL (Contd.)
  56. Lecture 56: Relationship between regular language and CFL
  57. Lecture 57: Pumping lemma for CFLs
  58. Lecture 58: Closer properties of CFLs
  59. Lecture 59: Turning Machine
  60. Lecture 60: Language accepted by a Turning machine
  61. Live Session 24-02-2021
  62. Live Session 26-03-2021

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Kharagpur.

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