NOC:Introduction to Automata, Languages and Computation


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