NPTEL : NOC:Introduction to Automata, Languages and Computation (Computer Science and Engineering)

Co-ordinators : Prof. Sourav Mukhopadhyay


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 6 - Building DFA (Continued...)

Lecture 7 - NFA (Nondeterministic Finite Automata)

Lecture 8 - Language of a NFA

Lecture 9 - Equivalence of DFAs and NFAs

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 (Continued...)

Lecture 18 - More on regular expression

Lecture 19 - Equivalence of NFA and regular expression

Lecture 20 - Equivalence of NFA and regular expression (Continued...)

Lecture 21 - DFA to Regular expression

Lecture 22 - DFA to Regular expression (Continued...)

Lecture 23 - Construction of regular expression from a DFA (example)

Lecture 24 - Closure properties of Regular Set

Lecture 25 - Closure properties of Regular Set (Continued...)

Lecture 26 - Substitution

Lecture 27 - Pumping Lemma

Lecture 28 - Application of the pumping lemma

Lecture 29 - More on Pumping lemma

Lecture 30 - Ardens Theorem

Lecture 31 - Minimization of FA

Lecture 32 - Minimization of FA (Continued...)

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 (Continued...)

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