Computer Science - Theory of Computation (English)

   Wednesday, April 23, 2025   

Starting a new Lecture Notes Series on Computer Science - Theory of Computation

Youtube Lecture Playlist Credits 

Channel Name: nptelhrd

So Let Us Start to This Journey of Learning 

Computer Science - Theory of Computation By Lecture Notes together!

Lecture 1: Mod-01 Lec-01 What is theory of computation?

Lecture 2: Mod-01 Lec-02 Introduction to finite automaton.

Lecture 3: Mod-01 Lec-03 Finite automata continued, deterministic finite automata(DFAs),

Lecture 4: Mod-01 Lec-04 Regular languages, their closure properties.

Lecture 5: Mod-01 Lec-05 DFAs solve set membership problems in linear time, pumping lemma.

Lecture 6: Mod-01 Lec-06 More examples of nonregular languages, proof of pumping lemma

Lecture 7: Mod-01 Lec-07 A generalization of pumping lemma, nondeterministic finite automata (NFAs)

Lecture 8: Mod-01 Lec-08 Formal description of NFA, language accepted by NFA, such languages are also regular.

Lecture 9: Mod-01 Lec-09 'Guess and verify' paradigm for nondeterminism.

Lecture 10: Mod- 01 Lec-10 NFA's with epsilon transitions.

Lecture 11: Mod-01 Lec-11 Regular expressions, they denote regular languages.

Lecture 12: Mod-01 Lec-12 Construction of a regular expression for a language given a DFA accepting it.

Lecture 13: Mod-01 Lec-13 Closure properties continued.

Lecture 14: Mod-01 Lec-14 Closure under reversal, use of closure properties.

Lecture 15: Mod-01 Lec-15 Decision problems for regular languages.

Lecture 16: Mod-01 Lec-16 About minimization of states of DFAs. Myhill-Nerode theorem.

Lecture 17: Mod-01 Lec-17 Continuation of proof of Myhill-Nerode theorem.

Lecture 18: Mod-01 Lec-18 Application of Myhill-Nerode theorem. DFA minimization.

Lecture 19: Mod-01 Lec-19 DFA minimization continued.

Lecture 20: Mod-01 Lec-20 Introduction to context free languages (cfls)

Lecture 21: Mod-01 Lec-21 Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls.

Lecture 22: Mod-01 Lec-22 Parse trees, inductive proof that L is L(G). All regular languages are context free.

Lecture 23: Mod-01 Lec-23 Towards Chomsky normal forms: elimination of useless symbols

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

Lecture 25: Mod-01 Lec-25 Elimination of unit productions. Converting a cfg into Chomsky normal form.

Lecture 26: Mod-01 Lec-26 Pumping lemma for cfls. Adversarial paradigm.

Lecture 27: Mod-01 Lec-27 Completion of pumping lemma proof

Lecture 28: Mod-01 Lec-28 Closure properties continued. cfls not closed under complementation.

Lecture 29: Mod-01 Lec-29 Another example of a cfl whose complement is not a cfl. Decision problems for cfls.

Lecture 30: Mod-01 Lec-30 More decision problems. CYK algorithm for membership decision.

Lecture 31: Mod-01 Lec-31 Introduction to pushdown automata (pda).

Lecture 32: Mod-01 Lec-32 pda configurations, acceptance notions for pdas. Transition diagrams for pdas

Lecture 33: Mod-01 Lec-33 Equivalence of acceptance by empty stack and acceptance by final state.

Lecture 34: Mod-01 Lec-34 Turing machines (TM): motivation, informal definition, example, transition diagram.

Lecture 35: Mod-01 Lec-35 Execution trace, another example (unary to binary conversion).

Lecture 36: Mod-01 Lec-36 Example continued. Finiteness of TM description

Lecture 37: Mod-01 Lec-37 Notion of non-acceptance or rejection of a string by a TM. Multitrack TM

Lecture 38: Mod-01 Lec-38 Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM).

Lecture 39: Mod-01 Lec-39 Counter machines and their equivalence to basic TM model.

Lecture 40: Mod-01 Lec-40 TMs can simulate computers, diagonalization proof.

Lecture 41: Mod-01 Lec-41 Existence of non-r.e. languages, recursive languages, notion of decidability.

Lecture 42: Mod-01 Lec-42 Separation of recursive and r.e. classes, halting problem and its undecidability.