| 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 |