Lecture 1 - What is theory of computation? Set membership problem, basic notions like alphabet, strings, formal languages

Lecture 3 - Finite automata continued, deterministic finite automata(DFAs), language accepted by a DFA

Lecture 6 - More examples of nonregular languages, proof of pumping lemma, pumping lemma as a game, converse of pumping lemma does not hold

Lecture 7 - A generalization of pumping lemma, nondeterministic finite automata (NFAs), computation trees for NFAs

Lecture 12 - Construction of a regular expression for a language given a DFA accepting it. Algebraic closure properies of regular languages

Lecture 20 - Introduction to context free languages (cfls) and context free grammars (cfgs). Derivation of strings by cfgs

Lecture 23 - Towards Chomsky normal forms: elimination of useless symbols, analysis of reachable symbols, generating nonterminals, order of substeps matter

Lecture 24 - Simplification of cfgs continued, Removal of epsilon productions: algorithm and its correctness

Lecture 25 - Elimination of unit productions. Converting a cfg into Chomsky normal form. Towards pumping lemma for cfls

Lecture 27 - Completion of pumping lemma proof. Examples of use of pumping lemma. Converse of lemma does not hold. Closure properties of cfls

Lecture 36 - Example continued. Finiteness of TM description, TM configuration, language acceptance, definition of recursively enumerable (r.e.) languages

Lecture 37 - Notion of non-acceptance or rejection of a string by a TM. Multitrack TM, its equivalence to standard TM. Multitape TMs