CS208: Automata Theory and Logic (Spring 2014)


Logistics


Relevant Textbooks

Main Reference Supplementary Reading

Grading

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

Topics

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

Schedule and Lecture Notes

# Date Description Textbook References
1 Jan 13 Introduction to automata theory [Slides ] Hopcroft, Motwani, and Ullman: Chapter 1
2 Jan 16 Introduction to automata theory [Slides ] Hopcroft, Motwani, and Ullman: Chapter 1
3 Jan 20 Introduction to propositional and first-order logic Guest lecture by Khushraj Madnani
4 Jan 21 Introduction to propositional and first-order logic Guest lecture by Khushraj Madnani
5 Jan 23 Deterministic Finite Automata: syntax and semantics (via computation and via extended transition function), some simple examples. [Slides ] Hopcroft, Motwani, and Ullman: Section 2.1 and 2.2, and Sipser Section 1.1
6 Jan 27 Deterministic Finite Automata: product construction for union and intersection [Slides ] Hopcroft, Motwani, and Ullman: Section 4.2.1, and Sipser Section 1.1
7 Jan 28 Deterministic Finite Automata: product construction contd., complementation, problems with concatenation and Kleene closure as a motivation for non-determinism. [Slides ] Hopcroft, Motwani, and Ullman: Section 4.2.1 and Section 2.3, and Sipser Section 1.2
8 Jan 30 Nondeterministic Finite Automata: the notion of acceptance via extended transition function and computation tree, $\varepsilon$- transitions, [Slides ] Hopcroft, Motwani, and Ullman: Section 2.3 to 2.5, and Sipser Section 1.2
9 Feb 3 Subset Construction [Slides ] Hopcroft, Motwani, and Ullman: Section 2.3.5 and 2.3.6, and Sipser Section 1.2
10 Feb 4 Regular Expressions: introduction, regular expressions to DFA conversion, and DFA to regular expressions conversion (by eliminating the states) [Slides ] Hopcroft, Motwani, and Ullman: Section 3.1, 3.2.2, and 3.2.3, and Sipser Section 1.3
11 Feb 6 Regular Expressions Contd.: Algebraic laws for regular expressions Hopcroft, Motwani, and Ullman: Section 3.4
* Feb 10 Class Cancelled
12 Feb 11 Regular Expressions: Correctness proof for the equivalence of DFA and Regular expressions Hopcroft, Motwani, and Ullman: Chapter 3
* Feb 12 [ Quiz 1 ]
* Feb 17 Mid-Semester Week
* Feb 19 [ Mid-Semester Exam ]
* Feb 20 Mid-Semester Week
13 Feb 24 Decision Properties of Regular Languages: Closure under Boolean operations, Regular Operations, Reversal, and homomorpshism Hopcroft, Motwani, and Ullman: Section 4.2
14 Feb 25 Closure under Homomorphism and inverse-homomorphism; decision properties of regular languages Hopcroft, Motwani, and Ullman: Section 4.2 and 4.3
15 Feb 27 Equivalence and Minimization of Automata [Slides ] Hopcroft, Motwani, and Ullman: Section 4.4
16 Mar 3 Equivalence and Minimization of Automata and Myhill-Nerode Theorem [Slides ] Hopcroft, Motwani, and Ullman: Section 4.4
17 Mar 4 Pumping Lemma for regular languages [Slides ] Hopcroft, Motwani, and Ullman: Section 4.1
18 Mar 6 Pumping Lemma (examples) [Slides ] Hopcroft, Motwani, and Ullman: Section 4.1
19 Mar 10 Chomsky's grammar hierarchy [Slides ] Hopcroft, Motwani, and Ullman: Chapter 5 and Sipser Chapter 2
20 Mar 11 Context-Free Languages [Slides ] Hopcroft, Motwani, and Ullman: Chapter 5 and Sipser Chapter 2
21 Mar 13 Context-Free Languages: Examples, and the concept of derivation, (leftmost and rightmost derivation), parse trees [Slides ] Hopcroft, Motwani, and Ullman: Chapter 5 and Sipser Chapter 2
* Mar 17 Institute holiday
* Mar 18 Lecture cancelled due to student's request
22 Mar 20 In-class Quiz.
23 Mar 24 Pushdown Automata [Slides ] Hopcroft, Motwani, and Ullman: Chapter 6 and Sipser Chapter 2
18 Mar 25 Equivalence of acceptance by empty stack and final states [Slides ] Hopcroft, Motwani, and Ullman: Chapter 6 and Sipser Chapter 2
24 Mar 27 Equivalence of CFGs and PDAs [Slides ] Hopcroft, Motwani, and Ullman: Chapter 6 and Sipser Chapter 2
* Mar 31 Institute Holiday
25 Apr 1 Properties of CFLs: Pumping lemma [Slides ] Hopcroft, Motwani, and Ullman: Chapter 7 and Sipser Chapter 2
26 Apr 3-15 Turing machines [Slides ] Hopcroft, Motwani, and Ullman: Chapter 8 and 9 and Sipser Chapter 3, 4, 5

Notes