An Introduction to The Theory of Computation

Preview 20:29

Notations and Terminology in Theory of Computation

Preview 32:43

An Introduction to Finite Automata and Regular Languages - Part 01

Preview 31:44

An Introduction to Finite Automata and Regular Languages - Part 02

Preview 27:30

Significance of Regular Languages and Regular Operations

Preview 16:11

Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 01

Preview 32:27

Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 02

Preview 12:25

An Introduction to Non-Deterministic Finite Automata (NFA)

Preview 34:06

Formal Definitions and Examples of Non-Deterministic Finite Automata(NFA)

Preview 16:22

Equivalence of NFA and DFA

Preview 42:02

Closure of Regular Languages Under Regular Operations(Using NFA)

Preview 38:31

Regular Expressions - Part 01

28:29

Regular Expressions - Part 02

Preview 17:25

Proving Equivalence of Regular Expression and DFA Through a GNFA

Preview 45:39

Pumping Lemma for Regular Languages - Part 01

Preview 32:09

Pumping Lemma for Regular Languages - Part 02

Preview 41:54

Distinguishability of Strings and Myhill-Nerode Theorem

Preview 30:04

Proving the Myhill-Nerode Theorem

Preview 39:54

An Introduction to Context-Free Languages - Part 01

Preview 27:16

An Introduction to Context-Free Languages - Part 02

Preview 38:44

Chomsky Normal Form

Preview 37:12

CYK Algorithm - Part 1

Preview 28:02

CYK Algorithm - Part 2 (Example)

Preview 19:00

Closure Properties of Context Free Languages

Preview 17:24

An Introduction to Push Down Automata

Preview 43:47

Normalizations in PDA and Intersection of Regular Language & CFL

Preview 21:54

Equivalence of Context Free Grammars and Push Down Automata - Part 01

Preview 25:12

Equivalence of Context Free Grammars and Push Down Automata - Part 02

Preview 33:45

Equivalence of Context Free Grammars and Push Down Automata - Part 03

Preview 33:45

Pumping Lemma for Context Free Languages

Preview 37:55

Examples of Pumping Lemma Usage for Context Free Languages

Preview 21:09

Formal Definition of a Turing Machine

Preview 37:17

Turing Recognizable & Decidable Languages and TM Examples

Preview 41:08

Multitape Turing Machine

Preview 26:47

Non-Deterministic Turing Machines

Preview 36:40

Equivalence of Deterministic and Nondeterministic TM

Preview 26:56

Church-Turing Thesis

Preview 29:52

Decidable Problems Concerning Regular Languages

Preview 26:36

Decidable Problems Concerning Context Free Languages

Preview 22:26

Countability of Sets

Preview 33:57

Proof of Existence of Undecidable Languages

Preview 26:42

Halting Problem

Preview 33:58

Co-Turing Recognizability

Preview 20:01

An Introduction to Mapping Reducibility

Preview 33:56

Examples of Proving Undecidability Using Reductions

Preview 37:56

Rice Theorem

Preview 34:32

Computation Histories

Preview 36:20

The Post Correspondence Problem

Preview 46:26

Checking Ambiguity in CFG is Undecidable

Preview 20:01

Time Complexity - Part 1

Preview 33:19

Time Complexity - Part 2

Preview 30:29

Non-Deterministic Polynomial Time - Part 1

Preview 32:03

Non-Deterministic Polynomial Time - Part 2

Preview 18:01

Verifiability and NP

Preview 38:29

Polynomial Time Reductions - Part 1

Preview 23:11

Polynomial Time Reductions - Part 2

Preview 27:18

NP-Completeness

Preview 14:41

Cook-Levin Theorem

Preview 35:21

Cook-Levin Theorem - Proof and Implications

Preview 43:41

CLIQUE and VERTEX-COVER is NP-Complete

Preview 44:37

HAM-PATH is NP-Complete

Preview 39:01

SUBSET-SUM is NP-Complete

Preview 39:15

Knapsack Problem

Preview 18:09

Integer Linear Program is NP-Complete

Preview 22:05

Space Complexity and its Complexity Classes

Preview 50:51

Logspace Reductions and NL-Completeness

Preview 50:51

Savitch's theorem

Preview 26:28

Results in Space Complexity

Preview 30:57

Summary and Concluding Remarks

Preview 17:05