mhrd logo inflibnet logo ugc logo

Module Details

Course : Theory Of Computation

Subject : Computer science

No. of Modules : 79

Level : FACULTY,STUDENTS,UG

Source : SwayamPrabha;Channel-13

Back

Sr. No. Title Creator/Author E-Text Video URL Metadata
1 Lecture 40 Prof. Raghunath Tewari - - Click Here
2 Lecture 39 Prof. Raghunath Tewari - - Click Here
3 Lecture 38 Prof. Raghunath Tewari - - Click Here
4 Lecture 37 Prof. Raghunath Tewari - - Click Here
5 Lecture 36 Prof. Raghunath Tewari - - Click Here
6 Lecture 35 Prof. Raghunath Tewari - - Click Here
7 Lecture 34 Prof. Raghunath Tewari - - Click Here
8 Lecture 33 Prof. Raghunath Tewari - - Click Here
9 Lecture 32 Prof. Raghunath Tewari - - Click Here
10 Lecture 31 Prof. Raghunath Tewari - - Click Here
11 Lecture 30 Prof. Raghunath Tewari - - Click Here
12 Lecture 27 Prof. Raghunath Tewari - - Click Here
13 Lecture 26 Prof. Raghunath Tewari - - Click Here
14 Lecture 25 Prof. Raghunath Tewari - - Click Here
15 Lecture 24 Prof. Raghunath Tewari - - Click Here
16 Lecture 23 Prof. Raghunath Tewari - - Click Here
17 Lecture 22 Prof. Raghunath Tewari - - Click Here
18 Lecture 21 Prof. Raghunath Tewari - - Click Here
19 Lecture-23-towards chomsky normal forms: elimination of useless symbols, analysis of reachable symbols, generating nonterminals, order of substeps matter. Prof. Somenath Biswas - - Click Here
20 Lecture-25-elimination of unit productions. converting a cfg into chomsky normal form. towards pumping lemma for cfls Prof. Somenath Biswas - - Click Here
21 Lecture-20-introduction to context free languages (cfls) and context free grammars (cfgs). derivation of strings by cfgs. Prof. Somenath Biswas - - Click Here
22 Lecture-24-simplification of cfgs continued, removal of epsilon productions: algorithm and its correctness. Prof. Somenath Biswas - - Click Here
23 Lecture-22-parse trees, inductive proof that l is l(g). all regular languages are context free. Prof. Somenath Biswas - - Click Here
24 Lecture-21-languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls. Prof. Somenath Biswas - - Click Here
25 Lecture-18-application of myhill-nerode theorem. dfa minimization. Prof. Somenath Biswas - - Click Here
26 Lecture-17-continuation of proof of myhill-nerode theorem. Prof. Somenath Biswas - - Click Here
27 Lecture-19-dfa minimization continued. Prof. Somenath Biswas - - Click Here
28 Lecture-06-more examples of nonregular languages, proof of pumping lemma, pumping lemma as a game, converse of pumping lemma does not hold. Prof. Somenath Biswas - - Click Here
29 Lecture-01 what is theory of computation? set membership problem, basic notions like alphabet, strings, formal languages. Prof. Somenath Biswas - - Click Here
30 Lecture-07-a generalization of pumping lemma, nondeterministic finite automata (nfas), computation trees for nfas. Prof. Somenath Biswas - - Click Here
31 Lecture-03-finite automata continued, deterministic finite automata(dfas), language accepted by a dfa. Prof. Somenath Biswas - - Click Here
32 Lecture-32-pda configurations, acceptance notions for pdas. transition diagrams for pdas Prof. Somenath Biswas - - Click Here
33 Lecture-05-dfas solve set membership problems in linear time, pumping lemma. Prof. Somenath Biswas - - Click Here
34 Lecture-04-regular languages, their closure properties. Prof. Somenath Biswas - - Click Here
35 Lecture-31-introduction to pushdown automata (pda). Prof. Somenath Biswas - - Click Here
36 Lecture-02-introduction to finite automaton. Prof. Somenath Biswas - - Click Here
37 Lecture-42-separation of recursive and r.e. classes, halting problem and its undecidability. Prof. Somenath Biswas - - Click Here
38 Lecture-27-completion of pumping lemma proof. examples of use of pumping lemma. converse of lemma does not hold. closure properties of cfls. Prof. Somenath Biswas - - Click Here
39 Lecture-29-another example of a cfl whose complement is not a cfl. decision problems for cfls. Prof. Somenath Biswas - - Click Here
40 Lecture-28-closure properties continued. cfls not closed under complementation. Prof. Somenath Biswas - - Click Here
41 Lecture-30-more decision problems. cyk algorithm for membership decision. Prof. Somenath Biswas - - Click Here
42 Lecture-26-pumping lemma for cfls. adversarial paradigm. Prof. Somenath Biswas - - Click Here
43 Lecture-12-construction of a regular expression for a language given a dfa accepting it. algebraic closure properies of regular languages. Prof. Somenath Biswas - - Click Here
44 Lecture-08-formal description of nfa, language accepted by nfa, such languages are also regular. Prof. Somenath Biswas - - Click Here
45 Lecture-16-about minimization of states of dfas. myhill-nerode theorem. Prof. Somenath Biswas - - Click Here
46 Lecture-11-regular expressions, they denote regular languages. Prof. Somenath Biswas - - Click Here
47 Lecture-14-closure under reversal, use of closure properties. Prof. Somenath Biswas - - Click Here
48 Lecture-09-'guess and verify' paradigm for nondeterminism. Prof. Somenath Biswas - - Click Here
49 Lecture-15-decision problems for regular languages. Prof. Somenath Biswas - - Click Here
50 Lecture-10-nfa's with epsilon transitions. Prof. Somenath Biswas - - Click Here
51 Lecture-13-closure properties continued. Prof. Somenath Biswas - - Click Here
52 Lecture-36-example continued. finiteness of tm description, tm configuration, language acceptance, definition of recursively enumerable (r.e.) languages. Prof. Somenath Biswas - - Click Here
53 Lecture-37-notion of non-acceptance or rejection of a string by a tm. multitrack tm, its equivalence to standard tm. multitape tms. Prof. Somenath Biswas - - Click Here
54 Lecture-38-simulation of multitape tms by basic model. nondeterministic tm (ndtm). equivalence of ndtms with deterministic tms. Prof. Somenath Biswas - - Click Here
55 Lecture-34-turing machines (tm): motivation, informal definition, example, transition diagram. Prof. Somenath Biswas - - Click Here
56 Lecture-41-existence of non-r.e. languages, recursive languages, notion of decidability. Prof. Somenath Biswas - - Click Here
57 Lecture-33-equivalence of acceptance by empty stack and acceptance by final state. Prof. Somenath Biswas - - Click Here
58 Lecture-35-execution trace, another example (unary to binary conversion). Prof. Somenath Biswas - - Click Here
59 Lecture-39-counter machines and their equivalence to basic tm model. Prof. Somenath Biswas - - Click Here
60 Lecture-40-tms can simulate computers, diagonalization proof. Prof. Somenath Biswas - - Click Here
61 Turing machine and halting B.ThanaSekar - - Click Here
62 Turing machines B.ThanaSekar - - Click Here
63 Linear bounded automation and context sensitive languages B.ThanaSekar - - Click Here
64 Transition diagram for turing machines B.ThanaSekar - - Click Here
65 Closure properties of cfg B.ThanaSekar - - Click Here
66 Context free grammar B.ThanaSekar - - Click Here
67 Turing machines B.ThanaSekar - - Click Here
68 Closure properties B.ThanaSekar - - Click Here
69 Cfg B.ThanaSekar - - Click Here
70 Closure properties of regular languages B.ThanaSekar - - Click Here
71 Parse tree and ambiguous grammar B.ThanaSekar - - Click Here
72 Regular expressions B.ThanaSekar - - Click Here
73 Regular expressions B.ThanaSekar - - Click Here
74 Regular expressions B.ThanaSekar - - Click Here
75 Cfg to pda B.ThanaSekar - - Click Here
76 Regular languages B.ThanaSekar - - Click Here
77 Epsilon nfa B.ThanaSekar - - Click Here
78 Nfa to dfa B.ThanaSekar - - Click Here
79 Nfa B.ThanaSekar - - Click Here