Theory of Computation by Somenath Biswas (IIT Kanpur)

# click the upper-left icon to select videos from the playlist

source: nptelhrd    2014年6月27日
Computer Science - Theory of Computation by Prof. Somenath Biswas, Computer Science and Engineering, IIT Kanpur. For more details on NPTEL visit http://nptel.ac.in

01 What is theory of computation? 51:52
02 Introduction to finite automaton. 1:01:04
03 Finite automata continued, deterministic finite automata(DFAs), 48:39
04 Regular languages, their closure properties. 1:03:57
05 DFAs solve set membership problems in linear time, pumping lemma. 55:20
06 More examples of nonregular languages, proof of pumping lemma 57:22
07 A generalization of pumping lemma, nondeterministic finite automata (NFAs) 1:01:34
08 Formal description of NFA, language accepted by NFA, such languages are also regular. 55:04
09 'Guess and verify' paradigm for nondeterminism. 53:50
10 NFA's with epsilon transitions. 1:03:27
11 Regular expressions, they denote regular languages. 59:33
12 Construction of a regular expression for a language given a DFA accepting it. 54:52
13 Closure properties continued. 1:01:07
14 Closure under reversal, use of closure properties. 46:44
15 Decision problems for regular languages. 55:30
16 About minimization of states of DFAs. Myhill-Nerode theorem. 49:00
17 Continuation of proof of Myhill-Nerode theorem. 55:07
18 Application of Myhill-Nerode theorem. DFA minimization. 1:00:03
19 DFA minimization continued. 57:06
20 Introduction to context free languages (cfls) 55:49
21 Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls. 56:11
22 Parse trees, inductive proof that L is L(G). All regular languages are context free. 52:31
23 Towards Chomsky normal forms: elimination of useless symbols 55:26
24 Simplification of cfgs continued, Removal of epsilon productions 1:07:16
25 Elimination of unit productions. Converting a cfg into Chomsky normal form. 55:32
26 Pumping lemma for cfls. Adversarial paradigm. 55:01
27 Completion of pumping lemma proof 52:52
28 Closure properties continued. cfls not closed under complementation. 55:31
29 Another example of a cfl whose complement is not a cfl. Decision problems for cfls. 45:30
30 More decision problems. CYK algorithm for membership decision. 53:17
31 Introduction to pushdown automata (pda). 56:02
32 pda configurations, acceptance notions for pdas. Transition diagrams for pdas 56:05
33 Equivalence of acceptance by empty stack and acceptance by final state. 48:08
34 Turing machines (TM): motivation, informal definition, example, transition diagram. 1:10:33
35 Execution trace, another example (unary to binary conversion). 43:19
36 Example continued. Finiteness of TM description 46:22
37 Notion of non-acceptance or rejection of a string by a TM. Multitrack TM 58:37
38 Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM). 58:55
39 Counter machines and their equivalence to basic TM model. 56:05
40 TMs can simulate computers, diagonalization proof. 58:42
41 Existence of non-r.e. languages, recursive languages, notion of decidability. 1:01:02
42 Separation of recursive and r.e. classes, halting problem and its undecidability. 1:03:00