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