Learn · NPTEL

Course10610519662 lectures

Introduction to Automata, Languages and Computation

Prof. Sourav Mukhopadhyay · IIT Kharagpur

Start with lecture 1 At NPTEL

Lectures

WEEK 1

  1. Lecture 1 : Deterministic Finite Automata (DFA) Video
  2. Lecture 2 : Input alphabet Video
  3. Lecture 3 : Extended transition function Video
  4. Lecture 4 : Language of DFA Video
  5. Lecture 5 : Building DFA Video

WEEK 2

  1. Lecture 06:Building DFA (contd.) Video
  2. Lecture 07: NFA (Nondeterministic Finite Automata) Video
  3. Lecture 08: Language of a NFA Video
  4. Lecture 09: Equivalence of DFA's and NFA's Video
  5. Lecture 10: Subset Construction Video

WEEK 3

  1. Lecture 11 : ϵ-NFA Video
  2. Lecture 12 : Extended transition function of 𝜖-NFA Video
  3. Lecture 13 : Language of 𝜖-NFA Video
  4. Lecture 14 : 𝜖-NFA to NFA Video
  5. Lecture 15 : 𝜖-NFA to DFA Video

WEEK 4

  1. Lecture 16 : Regular expression Video
  2. Lecture 17 : Regular expression (Contd.) Video
  3. Lecture 18 : More on regular expression Video
  4. Lecture 19 : Equivalence of 𝜖-NFA and regular expression Video
  5. Lecture 20 : Equivalence of 𝜖-NFA and regular expression (Contd.) Video

WEEK 5

  1. Lecture 21: DFA to Regular expression Video
  2. Lecture 22: DFA to Regular expression (Contd.) Video
  3. Lecture 23: Construction of regular expression from a DFA (example) Video
  4. Lecture 24: Closure properties of Regular Set Video
  5. Lecture 25: Closure properties of Regular Set (Contd.) Video

WEEK 6

  1. Lecture 26 : Substitution Video
  2. Lecture 27 : Pumping Lemma Video
  3. Lecture 28 : Application of the pumping lemma Video
  4. Lecture 29 : More on Pumping lemma Video
  5. Lecture 30 : Arden's Theorem Video

WEEK 7

  1. Lecture 31: Minimization of FA Video
  2. Lecture 32: Minimization of FA (Cont.) Video
  3. Lecture 33: Two way FA Video
  4. Lecture 34: Finite automata with output Video
  5. Lecture 35: Equivalence of Moore and Mealy machine Video

WEEK 8

  1. Lecture 36: Context free grammars (CFG) Video
  2. Lecture 37: Context free language (CFL) Video
  3. Lecture 38: More example on CFL Video
  4. Lecture 39: More on CFG Video
  5. Lecture 40: Derivation Tree/Parse Tree Video

WEEK 9

  1. Lecture 41 : Leftmost and Rightmost derivations Video
  2. Lecture 42 : Ambiguity in CFG Video
  3. Lecture 43 : Simplification of CFG Video
  4. Lecture 44 : Algorithms to construct reduced grammar Video
  5. Lecture 45 : Elimination of Null and Unit productions Video

WEEK 10

  1. Lecture 46 : Chomsky Normal Form (CNF) Video
  2. Lecture 47 : Greibach Normal Form (GNF) Video
  3. Lecture 48 : Pushdown Automata (PDA) Video
  4. Lecture 49 : Language accepted by PDA Video
  5. Lecture 50 : Example of a language accepted by PDA Video

WEEK 11

  1. Lecture 51 : Deterministic PDA Video
  2. Lecture 52 : Equivalence of language accepted Video
  3. Lecture 53 : Equivalence PDA Video
  4. Lecture 54 : Equivalence PDA and CFL Video
  5. Lecture 55 : Equivalence PDA and CFL (Contd.) Video

WEEK 12

  1. Lecture 56: Relationship between regular language and CFL Video
  2. Lecture 57: Pumping lemma for CFLs Video
  3. Lecture 58: Closer properties of CFLs Video
  4. Lecture 59: Turning Machine Video
  5. Lecture 60: Language accepted by a Turning machine Video

Live Session

  1. Live Session 24-02-2021 Video
  2. Live Session 26-03-2021 Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Kharagpur
Department
Computer Science and Engineering
Teacher
Prof. Sourav Mukhopadhyay
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