Modules / Lectures
Module NameDownload

Sl.No Chapter Name English
1Lecture-01 What is theory of computation? Set membership problem, basic notions like alphabet, strings, formal languages.PDF unavailable
2Lecture-02-Introduction to finite automaton.PDF unavailable
3Lecture-03-Finite automata continued, deterministic finite automata(DFAs), language accepted by a DFA.PDF unavailable
4Lecture-04-Regular languages, their closure properties.PDF unavailable
5Lecture-05-DFAs solve set membership problems in linear time, pumping lemma.PDF unavailable
6Lecture-06-More examples of nonregular languages, proof of pumping lemma, pumping lemma as a game, converse of pumping lemma does not hold.PDF unavailable
7Lecture-07-A generalization of pumping lemma, nondeterministic finite automata (NFAs), computation trees for NFAs.PDF unavailable
8Lecture-08-Formal description of NFA, language accepted by NFA, such languages are also regular.PDF unavailable
9Lecture-09-'Guess and verify' paradigm for nondeterminism.PDF unavailable
10Lecture-10-NFA's with epsilon transitions.PDF unavailable
11Lecture-11-Regular expressions, they denote regular languages.PDF unavailable
12Lecture-12-Construction of a regular expression for a language given a DFA accepting it. Algebraic closure properies of regular languages.PDF unavailable
13Lecture-13-Closure properties continued.PDF unavailable
14Lecture-14-Closure under reversal, use of closure properties.PDF unavailable
15Lecture-15-Decision problems for regular languages.PDF unavailable
16Lecture-16-About minimization of states of DFAs. Myhill-Nerode theorem.PDF unavailable
17Lecture-17-Continuation of proof of Myhill-Nerode theorem.PDF unavailable
18Lecture-18-Application of Myhill-Nerode theorem. DFA minimization.PDF unavailable
19Lecture-19-DFA minimization continued.PDF unavailable
20Lecture-20-Introduction to context free languages (cfls) and context free grammars (cfgs). Derivation of strings by cfgs.PDF unavailable
21Lecture-21-Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls.PDF unavailable
22Lecture-22-Parse trees, inductive proof that L is L(G). All regular languages are context free.PDF unavailable
23Lecture-23-Towards Chomsky normal forms: elimination of useless symbols, analysis of reachable symbols, generating nonterminals, order of substeps matter.PDF unavailable
24Lecture-24-Simplification of cfgs continued, Removal of epsilon productions: algorithm and its correctness.PDF unavailable
25Lecture-25-Elimination of unit productions. Converting a cfg into Chomsky normal form. Towards pumping lemma for cflsPDF unavailable
26Lecture-26-Pumping lemma for cfls. Adversarial paradigm.PDF unavailable
27Lecture-27-Completion of pumping lemma proof. Examples of use of pumping lemma. Converse of lemma does not hold. Closure properties of cfls.PDF unavailable
28Lecture-28-Closure properties continued. cfls not closed under complementation.PDF unavailable
29Lecture-29-Another example of a cfl whose complement is not a cfl. Decision problems for cfls.PDF unavailable
30Lecture-30-More decision problems. CYK algorithm for membership decision.PDF unavailable
31Lecture-31-Introduction to pushdown automata (pda).PDF unavailable
32Lecture-32-pda configurations, acceptance notions for pdas. Transition diagrams for pdasPDF unavailable
33Lecture-33-Equivalence of acceptance by empty stack and acceptance by final state.PDF unavailable
34Lecture-34-Turing machines (TM): motivation, informal definition, example, transition diagram.PDF unavailable
35Lecture-35-Execution trace, another example (unary to binary conversion).PDF unavailable
36Lecture-36-Example continued. Finiteness of TM description, TM configuration, language acceptance, definition of recursively enumerable (r.e.) languages.PDF unavailable
37Lecture-37-Notion of non-acceptance or rejection of a string by a TM. Multitrack TM, its equivalence to standard TM. Multitape TMs.PDF unavailable
38Lecture-38-Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM). Equivalence of NDTMs with deterministic TMs.PDF unavailable
39Lecture-39-Counter machines and their equivalence to basic TM model.PDF unavailable
40Lecture-40-TMs can simulate computers, diagonalization proof.PDF unavailable
41Lecture-41-Existence of non-r.e. languages, recursive languages, notion of decidability.PDF unavailable
42Lecture-42-Separation of recursive and r.e. classes, halting problem and its undecidability.PDF unavailable

Sl.No Language Book link
1EnglishNot Available
2BengaliNot Available
3GujaratiNot Available
4HindiNot Available
5KannadaNot Available
6MalayalamNot Available
7MarathiNot Available
8TamilNot Available
9TeluguNot Available