Theory of Computation II - IIT_Kanpur

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

Mod-01 Lec-24 Simplification of cfgs continued, Removal of epsilon productions

12 Views
IIT_Kanpur
IIT_Kanpur
5 subscribers
0
In Development / Programming Languages

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
100% online learning from the world's best universities, organisations and Instructors
 0 Comments sort   Sort By


⁣Mod-01 Lec-12 Geometry of Crystals: Symmetry, Lattices (continued) and Miller Indices
01:08:13
⁣Mod-01 Lec-12 Geometry of Crystals: Symmetry, Lattices (continued) and Miller Indices
IIT_Kanpur
6 Views · 07 Nov 2019
Engineering
⁣Mod-01 Lec-14 Miller Indices (continued) and Crystal Structures
01:02:08
⁣Mod-01 Lec-14 Miller Indices (continued) and Crystal Structures
IIT_Kanpur
6 Views · 07 Nov 2019
Engineering
⁣Mod-01 Lec-21 Crystal Structures (continued) and Defects in Crystals
01:02:52
⁣Mod-01 Lec-21 Crystal Structures (continued) and Defects in Crystals
IIT_Kanpur
4 Views · 07 Nov 2019
Engineering
⁣Lecture - 9 Hydrogen Atom - Angular Solutions Continued
00:59:01
⁣Lecture - 9 Hydrogen Atom - Angular Solutions Continued
IIT_Madras
7 Views · 23 Oct 2019
Maths & Sciences
⁣Lecture - 8 Hydrogen Atom Angular Solutions Continued
00:59:15
⁣Lecture - 8 Hydrogen Atom Angular Solutions Continued
IIT_Madras
6 Views · 23 Oct 2019
Maths & Sciences
⁣Lecture - 5 Harmonic Oscillator (Continued)
00:55:49
⁣Lecture - 5 Harmonic Oscillator (Continued)
IIT_Madras
4 Views · 23 Oct 2019
Maths & Sciences
⁣Lecture 5 Logic Simplification
00:54:18
⁣Lecture 5 Logic Simplification
IIT_Madras
6 Views · 21 Oct 2019
Engineering
⁣Lecture - 40 Reflection at Dielectric boundaries (Continued)
00:57:49
⁣Lecture - 40 Reflection at Dielectric boundaries (Continued)
IIT_Madras
8 Views · 14 Oct 2019
Engineering
⁣Lecture-36-Skin Effect (Continued)
00:57:08
⁣Lecture-36-Skin Effect (Continued)
IIT_Madras
9 Views · 14 Oct 2019
Engineering
⁣Plane Stress Fracture Toughness Testing continued
00:51:33
⁣Plane Stress Fracture Toughness Testing continued
IIT_Madras
12 Views · 11 Oct 2019
Engineering
⁣Mod-01 Lec-12b Queuing theory -- I (Continued)
00:53:21
⁣Mod-01 Lec-12b Queuing theory -- I (Continued)
IIT_Madras
10 Views · 08 Oct 2019
Engineering
⁣Mod-01 Lec-31 Models in JIT continued
00:52:35
⁣Mod-01 Lec-31 Models in JIT continued
IIT_Madras
7 Views · 08 Oct 2019
Business
⁣Mod-01 Lec-24 Cell scheduling and sequencing continued
00:51:51
⁣Mod-01 Lec-24 Cell scheduling and sequencing continued
IIT_Madras
17 Views · 08 Oct 2019
Business
⁣Mod-01 Lec-21 Operator and task assignment continued
00:48:42
⁣Mod-01 Lec-21 Operator and task assignment continued
IIT_Madras
11 Views · 08 Oct 2019
Business
⁣Mod-01 Lec-02 Lecture-02-Review of Basic Thermodynamics Continued
00:48:41
⁣Mod-01 Lec-02 Lecture-02-Review of Basic Thermodynamics Continued
IIT_Madras
8 Views · 08 Oct 2019
Engineering
⁣Mod-09 Lec-38 Transportation and Distribution Models(continued)
00:50:15
⁣Mod-09 Lec-38 Transportation and Distribution Models(continued)
IIT_Madras
10 Views · 07 Oct 2019
Business
⁣Mod-07 Lec-19 Particle Removal: Wet Cleaning
00:50:14
⁣Mod-07 Lec-19 Particle Removal: Wet Cleaning
IIT_Madras
11 Views · 05 Oct 2019
Engineering
⁣Mod-07 Lec-18 Particle Removal: Methods
00:50:03
⁣Mod-07 Lec-18 Particle Removal: Methods
IIT_Madras
8 Views · 05 Oct 2019
Engineering
⁣AFD26 - Common-mode Feedback (continued).
00:48:34
⁣AFD26 - Common-mode Feedback (continued).
IIT_Madras
9 Views · 03 Oct 2019
Development