CS208: Automata Theory and Logic


Logistics


Relevant Textbooks

Main Reference Supplementary Reading

Grading

  • End-Semester Exams: 50%
  • Mid-Semester Exams: 30%
  • Quizzes: 10%
  • Class participation: 10%

Topics

    Part I: Two formal models of computation: finite automata and Turing machines

  1. Finite Memory "Automata" and their languages [trivedi]
  2. Turing Machines (Finite automata extended with an unbounded read/write tape) and their languages [akshayss]
    [Mid-semester Exams]

    Part II: Between finite automata and Turing machines: Expressiveness vs Efficiency

  3. Pushdown Automata (Finite memory automata extended with a "Stack") and their languages [supratik]
  4. Future Directions: Complexity Theory and Automata Theory [trivedi]

    [End-semester Exams]


Schedule and Lecture Notes

Date Description Textbook References
May 17 Introduction to automata theory and some background [Slides ] Hopcroft, Motwani, and Ullman: Chapter 1 –or– Sipser: Chapter 1
May 21 Finite Automata and their properties [Slides] Hopcroft, Motwani, and Ullman: Section 2.1, 2.2, and 2.3 –or– Sipser: Section 1.1
May 22 Tutorial class—no new concepts were introduced.
May 24 Nondeterminism and Alternation [Slides] Hopcroft, Motwani, and Ullman: Section 2.3, 2.4, 2.5, and 4.2–or–Sipser: Section 1.2
May 28 Regular Expressions [Slides] Hopcroft, Motwani, and Ullman: Chapter 3–or–Sipser: Section 1.3
May 29 Tutorial class—no new concepts were introduced.
May 31 Lecture postponed to June 3rd.
June 3 Pumping Lemma, Minimization, and Myhill-Nerode Theorem [Slides] Hopcroft, Motwani, and Ullman: Chapter 4–or–Sipser: Section 1.4
June 4 Definition of Turing machines, examples, variants, the Church Turing thesis [Slides] Hopcroft, Motwani, and Ullman: Chapter 8–or–Sipser: Chapter 3
June 5 Tutorial class—no new concepts were introduced. Quiz.  
June 7 Decidability (recursive) and Turing recognizability (r.e), Undecidable languages (the Halting problem), and some more properties of decidable and r.e languages [Slides] Hopcroft, Motwani, and Ullman: Chapter 9 –or–Sipser:Chapter 4
June 10 Reductions, more undecidable problems, PCP, and counter machine [Slides] .
June 11 Tutorial class  
June 12 Mid-Semester Exam.  
June 18 Pushdown automata (PDA), acceptance by final states and empty stack, non-deterministic and deterministic PDA, Introduction to context free grammars (CFG)  
June 19 More on context free grammars, tutorial  

Notes