COL 352: Introduction to Automata and Theory of Computation

Semester II 2018-2019

Instructor : Sandeep Sen

Lectures: (Slot H) Mon, Wed 11 - 11:50 , Thurs : 12 - 12:50 Venue LH 310

Office hours: W: 12 - 1

Teaching Assistants: Office hours/help session
  • Kapil Kumar office hours Mon 3:30-4:30 pm office ICTD lab
  • Anuj Dhawan office hours Thu 3:30-4:30p DB Lab Bharti 408
  • Ankush Phulia office hours Tue 5-6 pm DB Lab, Bharti 408
  • Prayas Sahni office hours Tue 12:30-1:30p ICDT Lab
  • Sruti Goyal office hours Wed 5-6pm, SIT 307
  • 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)

    Background Material in Discrete Structures

    Course notes (from past editions of a related course)

    (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,

    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