•
NaN / NaN
Back
Skip navigation
Search
Search with your voice
Computer Science - Theory of Computation
42
videos
647,492 views
Last updated on
Aug 11, 2015
Preview
Save course
Share
Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For more details on NPTEL visit
http://nptel.ac.in
Show more
nptelhrd
nptelhrd
Subscribe
Play all
Computer Science - Theory of Computation
nptelhrd
·
Course
42
videos
Last updated on
Aug 11, 2015
Save course
Share
Play
Comments
Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For more details on NPTEL visit http://nptel.ac.in
…
...More
...More
…
...More
...More
Play
Comments
nptelhrd
1
51:52
51:52
Now playing
Mod-01 Lec-01 What is theory of computation?
nptelhrd
nptelhrd
•
294K views
•
10 years ago
•
2
1:01:04
1:01:04
Now playing
Mod-01 Lec-02 Introduction to finite automaton.
nptelhrd
nptelhrd
•
92K views
•
10 years ago
•
3
48:39
48:39
Now playing
Mod-01 Lec-03 Finite automata continued, deterministic finite automata(DFAs),
nptelhrd
nptelhrd
•
66K views
•
10 years ago
•
4
1:03:57
1:03:57
Now playing
Mod-01 Lec-04 Regular languages, their closure properties.
nptelhrd
nptelhrd
•
48K views
•
10 years ago
•
5
55:20
55:20
Now playing
Mod-01 Lec-05 DFAs solve set membership problems in linear time, pumping lemma.
nptelhrd
nptelhrd
•
31K views
•
10 years ago
•
6
57:22
57:22
Now playing
Mod-01 Lec-06 More examples of nonregular languages, proof of pumping lemma
nptelhrd
nptelhrd
•
24K views
•
10 years ago
•
7
1:01:34
1:01:34
Now playing
Mod-01 Lec-07 A generalization of pumping lemma, nondeterministic finite automata (NFAs)
nptelhrd
nptelhrd
•
19K views
•
10 years ago
•
8
55:04
55:04
Now playing
Mod-01 Lec-08 Formal description of NFA, language accepted by NFA, such languages are also regular.
nptelhrd
nptelhrd
•
16K views
•
10 years ago
•
9
53:50
53:50
Now playing
Mod-01 Lec-09 'Guess and verify' paradigm for nondeterminism.
nptelhrd
nptelhrd
•
12K views
•
10 years ago
•
10
1:03:27
1:03:27
Now playing
Mod- 01 Lec-10 NFA's with epsilon transitions.
nptelhrd
nptelhrd
•
16K views
•
10 years ago
•
11
59:33
59:33
Now playing
Mod-01 Lec-11 Regular expressions, they denote regular languages.
nptelhrd
nptelhrd
•
23K views
•
10 years ago
•
12
54:52
54:52
Now playing
Mod-01 Lec-12 Construction of a regular expression for a language given a DFA accepting it.
nptelhrd
nptelhrd
•
15K views
•
10 years ago
•
13
1:01:07
1:01:07
Now playing
Mod-01 Lec-13 Closure properties continued.
nptelhrd
nptelhrd
•
10K views
•
10 years ago
•
14
46:44
46:44
Now playing
Mod-01 Lec-14 Closure under reversal, use of closure properties.
nptelhrd
nptelhrd
•
9.8K views
•
10 years ago
•
15
55:30
55:30
Now playing
Mod-01 Lec-15 Decision problems for regular languages.
nptelhrd
nptelhrd
•
12K views
•
10 years ago
•
16
49:00
49:00
Now playing
Mod-01 Lec-16 About minimization of states of DFAs. Myhill-Nerode theorem.
nptelhrd
nptelhrd
•
14K views
•
10 years ago
•
17
55:07
55:07
Now playing
Mod-01 Lec-17 Continuation of proof of Myhill-Nerode theorem.
nptelhrd
nptelhrd
•
10K views
•
10 years ago
•
18
1:00:03
1:00:03
Now playing
Mod-01 Lec-18 Application of Myhill-Nerode theorem. DFA minimization.
nptelhrd
nptelhrd
•
11K views
•
10 years ago
•
19
57:06
57:06
Now playing
Mod-01 Lec-19 DFA minimization continued.
nptelhrd
nptelhrd
•
8.3K views
•
10 years ago
•
20
55:49
55:49
Now playing
Mod-01 Lec-20 Introduction to context free languages (cfls)
nptelhrd
nptelhrd
•
39K views
•
10 years ago
•
21
56:11
56:11
Now playing
Mod-01 Lec-21 Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls.
nptelhrd
nptelhrd
•
20K views
•
10 years ago
•
22
52:31
52:31
Now playing
Mod-01 Lec-22 Parse trees, inductive proof that L is L(G). All regular languages are context free.
nptelhrd
nptelhrd
•
12K views
•
10 years ago
•
23
55:26
55:26
Now playing
Mod-01 Lec-23 Towards Chomsky normal forms: elimination of useless symbols
nptelhrd
nptelhrd
•
12K views
•
10 years ago
•
24
1:07:16
1:07:16
Now playing
Mod-01 Lec-24 Simplification of cfgs continued, Removal of epsilon productions
nptelhrd
nptelhrd
•
8.8K views
•
10 years ago
•
25
55:32
55:32
Now playing
Mod-01 Lec-25 Elimination of unit productions. Converting a cfg into Chomsky normal form.
nptelhrd
nptelhrd
•
9.1K views
•
10 years ago
•
26
55:01
55:01
Now playing
Mod-01 Lec-26 Pumping lemma for cfls. Adversarial paradigm.
nptelhrd
nptelhrd
•
14K views
•
10 years ago
•
27
52:52
52:52
Now playing
Mod-01 Lec-27 Completion of pumping lemma proof
nptelhrd
nptelhrd
•
8.5K views
•
10 years ago
•
28
Mod-01 Lec-28 Closure properties continued. cfls not closed under complementation.
nptelhrd
nptelhrd
•
8.2K views
•
10 years ago
•
29
Mod-01 Lec-29 Another example of a cfl whose complement is not a cfl. Decision problems for cfls.
nptelhrd
nptelhrd
•
6.3K views
•
10 years ago
•
30
Mod-01 Lec-30 More decision problems. CYK algorithm for membership decision.
nptelhrd
nptelhrd
•
9.7K views
•
10 years ago
•
31
Mod-01 Lec-31 Introduction to pushdown automata (pda).
nptelhrd
nptelhrd
•
31K views
•
10 years ago
•
32
Mod-01 Lec-32 pda configurations, acceptance notions for pdas. Transition diagrams for pdas
nptelhrd
nptelhrd
•
13K views
•
10 years ago
•
33
Mod-01 Lec-33 Equivalence of acceptance by empty stack and acceptance by final state.
nptelhrd
nptelhrd
•
27K views
•
10 years ago
•
34
Mod-01 Lec-34 Turing machines (TM): motivation, informal definition, example, transition diagram.
nptelhrd
nptelhrd
•
39K views
•
10 years ago
•
35
Mod-01 Lec-35 Execution trace, another example (unary to binary conversion).
nptelhrd
nptelhrd
•
14K views
•
10 years ago
•
36
Mod-01 Lec-36 Example continued. Finiteness of TM description
nptelhrd
nptelhrd
•
9.6K views
•
10 years ago
•
37
Mod-01 Lec-37 Notion of non-acceptance or rejection of a string by a TM. Multitrack TM
nptelhrd
nptelhrd
•
8.4K views
•
10 years ago
•
38
Mod-01 Lec-38 Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM).
nptelhrd
nptelhrd
•
10K views
•
10 years ago
•
39
Mod-01 Lec-39 Counter machines and their equivalence to basic TM model.
nptelhrd
nptelhrd
•
12K views
•
10 years ago
•
40
Mod-01 Lec-40 TMs can simulate computers, diagonalization proof.
nptelhrd
nptelhrd
•
8K views
•
10 years ago
•
41
Mod-01 Lec-41 Existence of non-r.e. languages, recursive languages, notion of decidability.
nptelhrd
nptelhrd
•
10K views
•
10 years ago
•
42
Mod-01 Lec-42 Separation of recursive and r.e. classes, halting problem and its undecidability.
nptelhrd
nptelhrd
•
9.9K views
•
10 years ago
•