NPTEL : Formal Languages and Automata Theory (Mathematics)

Co-ordinators : Dr. K.V. Krishna, Dr. Diganta Goswami


Lecture 1 - Introduction

Lecture 2 - Alphabet, Strings, Languages

Lecture 3 - Finite Representation

Lecture 4 - Grammars (CFG)

Lecture 5 - Derivation Trees

Lecture 6 - Regular Grammars

Lecture 7 - Finite Automata

Lecture 8 - Nondeterministic Finite Automata

Lecture 9 - NFA <=> DFA

Lecture 10 - Myhill-Nerode Theorem

Lecture 11 - Minimization

Lecture 12 - RE => FA

Lecture 13 - FA => RE

Lecture 14 - FA <=> RG

Lecture 15 - Variants of FA

Lecture 16 - Closure Properties of RL

Lecture 17 - Homomorphism

Lecture 18 - Pumping Lemma

Lecture 19 - Simplification of CFG

Lecture 20 - Normal Forms of CFG

Lecture 21 - Properties of CFLs

Lecture 22 - Pushdown Automata

Lecture 23 - PDA <=> CFG

Lecture 24 - Turing Machines

Lecture 25 - Turing Computable Functions

Lecture 26 - Combining Turing Machines

Lecture 27 - Multi Input

Lecture 28 - Turing Decidable Languages

Lecture 29 - Varients of Turing Machines

Lecture 30 - Structured Grammars

Lecture 31 - Decidability

Lecture 32 - Undecidability 1

Lecture 33 - Undecidability 2

Lecture 34 - Undecidability 3

Lecture 35 - Time Bounded Turing Machines

Lecture 36 - P and NP

Lecture 37 - NP-Completeness

Lecture 38 - NP-Complete Problems 1

Lecture 39 - NP-Complete Problems 2

Lecture 40 - NP-Complete Problems 3

Lecture 41 - Chomsky Hierarchy