Modules / Lectures

Sl.No | Chapter Name | English |
---|---|---|

1 | Lecture-01 What is theory of computation? Set membership problem, basic notions like alphabet, strings, formal languages. | Download Verified |

2 | Lecture-02-Introduction to finite automaton. | Download Verified |

3 | Lecture-03-Finite automata continued, deterministic finite automata(DFAs), language accepted by a DFA. | Download Verified |

4 | Lecture-04-Regular languages, their closure properties. | Download Verified |

5 | Lecture-05-DFAs solve set membership problems in linear time, pumping lemma. | Download Verified |

6 | Lecture-06-More examples of nonregular languages, proof of pumping lemma, pumping lemma as a game, converse of pumping lemma does not hold. | Download Verified |

7 | Lecture-07-A generalization of pumping lemma, nondeterministic finite automata (NFAs), computation trees for NFAs. | Download Verified |

8 | Lecture-08-Formal description of NFA, language accepted by NFA, such languages are also regular. | Download Verified |

9 | Lecture-09-'Guess and verify' paradigm for nondeterminism. | PDF unavailable |

10 | Lecture-10-NFA's with epsilon transitions. | Download Verified |

11 | Lecture-11-Regular expressions, they denote regular languages. | Download Verified |

12 | Lecture-12-Construction of a regular expression for a language given a DFA accepting it. Algebraic closure properies of regular languages. | Download Verified |

13 | Lecture-13-Closure properties continued. | Download Verified |

14 | Lecture-14-Closure under reversal, use of closure properties. | Download Verified |

15 | Lecture-15-Decision problems for regular languages. | Download Verified |

16 | Lecture-16-About minimization of states of DFAs. Myhill-Nerode theorem. | Download Verified |

17 | Lecture-17-Continuation of proof of Myhill-Nerode theorem. | Download Verified |

18 | Lecture-18-Application of Myhill-Nerode theorem. DFA minimization. | Download Verified |

19 | Lecture-19-DFA minimization continued. | Download Verified |

20 | Lecture-20-Introduction to context free languages (cfls) and context free grammars (cfgs). Derivation of strings by cfgs. | Download Verified |

21 | Lecture-21-Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls. | Download Verified |

22 | Lecture-22-Parse trees, inductive proof that L is L(G). All regular languages are context free. | Download Verified |

23 | Lecture-23-Towards Chomsky normal forms: elimination of useless symbols, analysis of reachable symbols, generating nonterminals, order of substeps matter. | Download Verified |

24 | Lecture-24-Simplification of cfgs continued, Removal of epsilon productions: algorithm and its correctness. | Download Verified |

25 | Lecture-25-Elimination of unit productions. Converting a cfg into Chomsky normal form. Towards pumping lemma for cfls | Download Verified |

26 | Lecture-26-Pumping lemma for cfls. Adversarial paradigm. | Download Verified |

27 | Lecture-27-Completion of pumping lemma proof. Examples of use of pumping lemma. Converse of lemma does not hold. Closure properties of cfls. | Download Verified |

28 | Lecture-28-Closure properties continued. cfls not closed under complementation. | Download Verified |

29 | Lecture-29-Another example of a cfl whose complement is not a cfl. Decision problems for cfls. | Download Verified |

30 | Lecture-30-More decision problems. CYK algorithm for membership decision. | Download Verified |

31 | Lecture-31-Introduction to pushdown automata (pda). | Download Verified |

32 | Lecture-32-pda configurations, acceptance notions for pdas. Transition diagrams for pdas | Download Verified |

33 | Lecture-33-Equivalence of acceptance by empty stack and acceptance by final state. | Download Verified |

34 | Lecture-34-Turing machines (TM): motivation, informal definition, example, transition diagram. | Download Verified |

35 | Lecture-35-Execution trace, another example (unary to binary conversion). | Download Verified |

36 | Lecture-36-Example continued. Finiteness of TM description, TM configuration, language acceptance, definition of recursively enumerable (r.e.) languages. | Download Verified |

37 | Lecture-37-Notion of non-acceptance or rejection of a string by a TM. Multitrack TM, its equivalence to standard TM. Multitape TMs. | Download Verified |

38 | Lecture-38-Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM). Equivalence of NDTMs with deterministic TMs. | Download Verified |

39 | Lecture-39-Counter machines and their equivalence to basic TM model. | Download Verified |

40 | Lecture-40-TMs can simulate computers, diagonalization proof. | Download Verified |

41 | Lecture-41-Existence of non-r.e. languages, recursive languages, notion of decidability. | Download Verified |

42 | Lecture-42-Separation of recursive and r.e. classes, halting problem and its undecidability. | Download Verified |

Sl.No | Language | Book link |
---|---|---|

1 | English | Not Available |

2 | Bengali | Not Available |

3 | Gujarati | Not Available |

4 | Hindi | Not Available |

5 | Kannada | Not Available |

6 | Malayalam | Not Available |

7 | Marathi | Not Available |

8 | Tamil | Not Available |

9 | Telugu | Not Available |