CS331: Theory of Computation
(Autumn 2001)

Teaching Staff

Instructor	Supratik Chakraborty
TA	Nitin S. Kulkarni

Replace the "[AT]" and spaces in the email addresses by @ if you need to send email.

All scores and grades have been posted. You can check your answer books till Dec 16 from my office in CFDVS.

Hours

What	When	Where
Lectures	Mon 9:30 Tue 11:30 Thu 10:30	Room A2, Maths Bldg.
Office hour	Fri 14:00 - 15:00 by appointment	Room S13, CSE Bldg or
		CFDVS Lab 1 (Maths Bldg basement).

Grading

Midterm	30%
Endterm	50%
Homeworks	15%
Class Notes	5%

All exams are open book and notes.
Homeworks are due in class one week after they are given.
You are advised not to indulge in lengthy solutions. The problems are meant to test your understanding of the subject and your creativity. Late turn-ins will be penalized.
There is zero tolerance for dishonest means like copying solutions from others.
Anybody found indulging in such activities will be very severely penalized (including FF/FR grade).

Reading Material

Introduction to Automata Theory, Languages and Computation by J. E. Hopcroft and J. D. Ullman. Indian edition published by Narosa Publishing House.
Elements of the Theory of Computation by H. R. Lewis and C. H. Papadimitriou. Eastern economy edition published by Prentice Hall of India Pvt. Ltd.
Introduction to the Theory of Computation by Michael Sipser. PWS Publishing Company.
Class handouts, as and when necessary.

Class Notes Policy

To help absentee students catch up with missed lectures, we will follow the following policy:

Student with roll number i will take notes of lecture i, format it in LaTeX and forward it to the instructor within a week from the lecture.
The notes, after possible editing, will be put up in the Student Notes column of the Lecture Schedule section of this page.
Mutual exchange of note-taking responsibilities between students is allowed.

Tips for writing good class notes.

Homeworks, Practice Questions and Exams

Homework 1	Due Sep 3, 2001	Score histogram
Autumn 2000 Midterm
Practice Homework 2	Solutions
Midterm		Score histogram
Autumn 2000 Endterm	Ignore 4(b)
Endterm		Score histogram

Lecture Schedule

Date	Topics	Student notes
Jul 23	Logistics. Overview of simple proof techniques: contradiction, induction, pigeon-hole principle. Decomposing a proof goal into sequence of subgoals. Notions of alphabet, string, language	Notes
Jul 24	Notion of countability. Uncountability of the set of languages over a non-empty alphabet. Diagonalization argument	Notes
Jul 25	More on countability, Finite automata basics	Notes
Jul 30	Deterministic (DFA) and non-deterministic (NFA) finite automata, notion of non-deterministic computation, acceptance criteria	Notes
Jul 31	Equivalence of NFA and DFA: intuition and proof	Notes
Aug 2	NFAs with epsilon transitions, equivalence with epsilon-free NFAs	Notes
Aug 6	Regular expressions; Kleene's Theorem: equivalence of regular expressions and finite automata	Notes
Aug 7	Converting regular expressions to NFAs, and DFAs to regular expressions	Notes
Aug 9	Pumping Lemma (PL) for regular languages: Intuition and application in proving non-regularity of languages	Notes
Aug 13	More on PL; existence of non-regular languages satisfying PL	Notes
Aug 14	Slight generalization of PL for regular languages; closure of regular languages under simple set operations; notion of substitution	Notes
Aug 16	More on substitution; closure of regular languages under substitution; proving regular expression identities using substitution	Notes
Aug 20	Homomorphisms and inverse homomorphisms; quotients of regular languages with regular languages	Notes
Aug 21	Quotients of regular languages with arbitrary languages, Decision procedures for regular languages	Notes
Aug 23	Minimizing number of states in a DFA, Myhill-Nerode Theorem	Notes
Aug 27	Uniqueness (upto isomorphism) of minimal DFA. Introduction to context-free languages (CFL)	Notes
Aug 28	Context-free grammars (CFG), derivations, derivation trees	Notes
Aug 30	Equivalence of derivation trees and derivations, ambiguous grammars, inherently ambiguous CFLs	Notes
Sep 3	CFG simplification: removing useless symbols, removing epsilon productions	Notes
Sep 4	CFG simplification: removing epsilon and unit productions	Notes
Sep 6	Chomsky-Normal Form of CFG, Pumping Lemma for CFGs	Notes Clarifications
Sep 10	Basics of Pushdown Automata (PDA): notation, operation, acceptance of strings	Notes
Sep 11	PDA acceptance by final state and by empty stack, equivalence of the two notions	Notes
Sep 13	Equivalence of CFGs and PDAs: intuition and constructions	Notes
Sep 13 (Extra lecture)	Closure properties of CFLs: substitution, union, concatenation, Kleene closure, homomorphism, inverse homomorphism, intersection with regular languages; Non-closure under intersection and complement; Algorithms for checking emptiness, finiteness, membership for CFLs	Notes
Sep 24	More familiarity with CFLs and PDAs; Traits to look for when looking for CFLs; Ogden's Lemma	Notes
Sep 25	Ogden's Lemma: Intuition and applications; use of CFLs and PDAs in programming languages	Notes
Sep 27	Turing Machines (TM): description, acceptance by final states. Why study TMs? Example of problem without an algorithm	Notes
Oct 1	Acceptance by TM halting; equivalence between acceptance by final states and by halting; building simple TMs	Notes
Oct 4	TMs with two-way infinite tapes, multi-track tapes, multiple tapes with independent heads: equivalence with basic TM model	Notes
Oct 8	More on multi-tape TMs, non-deterministic TMs and equivalence with deterministic TMs	Notes
Oct 9	General-purpose computers and TMs; 2-stack machines and counter machines	Notes
Oct 11	Counter Machines and their power	Notes
Oct 15	Simplifying TMs: reducing no. of states, reducing no. of state symbols of single-tape TMs.	Notes

CS331: Theory of Computation (Autumn 2001)