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

## No comments:

Post a Comment