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


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