# 
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 firstorder logic

Guest lecture by Khushraj Madnani 
4 
Jan 21 
Introduction to propositional and firstorder 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 nondeterminism.
[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 
MidSemester Week


* 
Feb 19 
[ MidSemester Exam ]


* 
Feb 20 
MidSemester 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 inversehomomorphism; 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 MyhillNerode 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 
ContextFree Languages
[Slides ]

Hopcroft, Motwani, and Ullman: Chapter 5 and Sipser Chapter 2 
21 
Mar 13 
ContextFree 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 
Inclass 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 315 
Turing machines
[Slides ]

Hopcroft, Motwani, and Ullman: Chapter 8 and 9 and Sipser Chapter 3, 4, 5 