Raj Kamal
office hours Tue 4-5pm, SIT 309
Grading
The total will be computed as Minors 1 and 2 - 20% each, Major 40%, Quizes
and Assignments - 20%.
Attendence policy
The eligiility for audit pass (NP) and E grades, is minimum 75% attendence.
Students should abide by the attendence rules
stipulated by the Institute. Students failing to meet attendence requirements
will be dealt as per current institute policy.
Prerequisites: CSL105 (Discrete Structures or equivalent)
(uploaded classroom) Lectures)
Lecture 1 (Computation and Machines, some perspectives )
Lecture 2 (Language, membership, PCP )
Lecture 3 (Cardinality, diagonalization )
Lecture 4 (Finite State Automaton )
Lecture 5 (Characterizing a DFA)
Lecture 6 (More DFA examples)
Lecture 7 (NFA )
Lecture 8 (NFA-> DFA )
Lecture 9 (Regular Expr )
Lecture 10 (Reg Expr-> NFA )
Lecture 11 DFA -> (Reg Expr)
Lecture 12 Closure properties,PL
Lecture 13 Appl of PL
Lecture 14 Decision problems of RL
Lecture 15 Myhill Nerode Reln
Lecture 16 DFA minimization
Lecture 17 CFL
Lecture 18,19 Normal form,CYK algo
Lecture 20,21 PDA and eqv with CFG
Lecture 22,23 Properties of CFL, PL,
Lecture 25,26 Turing machine model
Lecture 27,28 Recursive and r.e., generators,
Tutorial Problems
Assignment submission penalty
For every day of delay, you will lose
additional 25%.
Make it a point to submit the assignments on the due date in class. No
midnight extensions. You can submit before if you are unable to come to the
lecture.
Lectures (from a previous version)
Lecture 2 (Language, decision, cardinality)
Lecture 3 (Diagonalization argument, discussion)
Lectures 4,5 (Finite State Automaton)
Lectures 6,7 (NFA)
Lectures 8 (Regular expressions)
Lectures 9,10 (r.e. and FA)
Lectures 11 (DFA to r.e.)
Lectures 12 (Pumping Lemma)
Lectures 13 (PL and closure properties)
Lectures 14 (Discussion)
Lecture 15,16 (Myhill Nerode Theorem)
Lecture 17 (Minimizing DFA )
Lecture 18 (Problem discussions)
Lecture 19 (Context Free Grammar)
Lecture 20 (CYK algorithm)
Lecture 21,22 (PDA)
Lecture 23 (Properties of CFL)
Lecture 24,25 (Turing machines)
Lecture 26,27 (Re languages and generators)
Lecture 28 (RAM model, counter machines)
Lecture 29, 30 (Properties of re, Universal TM )
Lecture 31 (Many-one TM computable reduction )
Lecture 32 (Rice's theorem for recursive index )
Lecture 33 (Undecidable problems on TM)
Lecture 34 (Time and Space Complexity)
Lecture 35 (Relationship between classes)
Lecture 36 (Classes P and NP)
Lecture 37 (Poly time redn and NPC)
Lecture 38 (Cook Levin Theorem)
Recommended : CSL201 (Data Structures)
Contents.
Formal Languages Regular Languages, Finite Automata, equivalence, minimization, Myhill Nerode
theorem, Introduction to non-determinism, Context Free Grammars, Pushdown
Automata, Equivalence and Applications
Computability : Turing Machines, Recursive and recursively enumerable sets, RAMs and
equivalence, Universal Turing Machine, Undecidability, Rices theorem for
recursive and re sets, Recursive function theory and equivalence, Church
Turing Thesis
Computational Complexity : Space Time complexity, Savitch's theorem,
Complexity classes, Complete problems, NP completeness, Cook-Levin
theorem and reductions
Reference books
Introduction to Automata Theory, Languages and Computation
by Hopcroft and Ullman, Pub: Narosa
Automata and Computability Kozen
Pub- Springer (Indian reprint available)
Sandeep Sen
Last modified: Wed Jan 1 2014