CS331: Theory of Computation
(Autumn 2003)

All scores and grades have been posted.

Teaching Staff

Instructor Supratik Chakraborty
Friendly TAs Navneet Kataria Ashish Ramesh Bhambhani


What When Where
Mon 9:30 Tue 11:35
Thurs 10:35
Room A2, Maths Bldg.
Office hour
Wed 15:00-16:00
CFDVS Lab 1 (Maths basement)

Lecture on Rescheduled to
Wed Aug 6
Tues July 29 8:30-9:25
Mon Aug 11
Thurs July 31, 10:35-11:30
Tues Aug 12
Fri Aug 1 8:30-9:25
Mon Sep 15
Tues Sep 9 9:30-10:30
Tues Sep 16
Wed Sep 10 10:30-11:30

TutorialsWhen Where
Tutorial 1
Mon Aug 11 9:30 - 10:30
Room A2, Maths Bldg
Tutorial 2
Mon Sept 1, 9:30 - 10:30
Room A2, Maths Bldg
Tutorial 3
Wed Oct 22, 8:30 - 9:30
Room A2, Maths Bldg
Tutorial 4
Sat Nov 1, 14:00 - 15:00
Room A2, Maths Bldg


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

Reading Material

Class Notes Policy

To help absentee students catch up with missed lectures, we will follow the following policy: Tips for writing good class notes.

Homeworks, Practice Questions and Exams

Homeworks for 2003
Homework 1 Due Mon Oct 13, 2003
Homework 2 Due Mon Nov 17, 2003
Homeworks from 2002
Homework 1 Solutions
Homework 2
Practice Problem Sets
Practice Problem Set 1
Practice Problem Set 2 Solutions
Practice Problem Set 3
Practice Problem Set 4 Solutions
Exams (earlier and current years)
Mid Semester Exam 2000
Mid Semester Exam 2001
Mid Semester Exam 2002
Mid Semester Exam 2003
End Semester Exam 2000 Ignore Questions 3, 4(a) and 7
End Semester Exam 2001 Ignore Question 4
End Semester Exam 2002 Ignore Question 3

Lecture Schedule

DateTopicsStudent Notes
Jul 22Logistics. Motivation for studying theory of computation. An example of a problem that cannot be solved by a computer. Notes [PS]
Jul 28Alphabet, strings, languages. Uncountability of the number of languages that can be formed from a simple alphabet. Formulation of computation problems as membership in a suitable language. Informal introduction to Turing Machine as a mechanism for deciding membership in a language. Simplification of Turing Machine model to finite state automaton. Notes [PS]
Jul 29Deterministic Finite Automata (DFA) basics and examples. Acceptance of strings by DFA. Language defined by a DFA Notes [PS]
Jul 29Non-deterministic Finite Automata (NFA) basics. Acceptance condition of NFA. Language defined by an NFA. Notes [PDF]
Jul 30NFAs continued. Equivalence of NFA and DFA. Advantage of using NFAs. Notes (not submitted)
Jul 31Example of how an NFA can provide a much more succinct representation of a language compared to a DFA. More on equivalence of NFA and DFA. Notes [PS]
Aug 1NFA with epsilon transitions. Converting an NFA with epsilon transitions to an equivalent NFA without epsilon transitions. Notes (submitted, not verified)
Aug 4 Equivalence of NFAs with and without epsilon transitions. Compactness of NFAs with epsilon transitions. Regular languages and regular grammars. Equivalence of regular grammars and DFAs. Notes (submitted, not verified)
Aug 5Regular expressions: syntax and semantics. Constructing an NFA with epsilon transitions from a regular expression. Notes (submitted, not verified)
Aug 14Constructing a regular expression for the language accepted by a DFA. Equivalence of regular expressions and DFAs. Summary of five alternative representations for regular languages. Notes (submitted, not verified)
Aug 18Closure of regular sets under union, intersection, complementation, finite number of Boolean operations. Pumping Lemma for regular languages. Notes (not submitted)
Aug 19More on Pumping Lemma. Proving languages non-regular using Pumping Lemma. Substitution as an operation to map symbols, strings and languages in one alphabet to languages in another alphabet. Substitution of regular languages. Notes (submitted, not verified)
Aug 21Closure of regular languages under substitution. Proving regular expression identities using substitution. Closure of regular languages under homomorphism and inverse homomorphism. Notes (submitted, not verified)
Aug 25More on inverse homomorphism. Proving non-regularity of languages using closure results. Reasoning about emptiness and finiteness of regular languages. Notes (not submitted)
Aug 26Quotients of regular languages with arbitrary languages. Reasoning about the minimum number of states needed to recognize a regular language. Notes (not submitted)
Aug 28The beauty of Myhill-Nerode Theorem. Proving languages regular and non-regular using Myhill-Nerode Theorem. Intuition behind minimization of DFA Notes (not submitted)
Sep 1 Algorithm for minimizing a given DFA: soundness and completeness proofs Notes (not submitted)
Sep 2 Uniqueness (upto isomorphism) of the minimized DFA for a given regular language. Use in checking equality of languages. Basics of Context Free Languages (CFL) Notes (not submitted)
Sep 4 Context Free Grammars (CFG). Derivation of strings from non-terminals. Leftmost and rightmost derivations. Parse trees as capturing all derivation sequences. Notes (not submitted)
Sep 8 Ambiguous grammars. Removing ambiguity in specific cases. Ambiguous grammars for arithmetic expressions. Inherently ambiguous languages Notes (not submitted)
Sep 9 Effect of grammar ambiguity on interpretation of arithmetic expressions. Modifying grammars to enforce operator precedence in arithmetic expressions Notes (not submitted)
Sep 9 More on modifying grammars to enforce operator precedence. Removing epsilon production rules from CFGs.. Notes (not submitted)
Sep 10 Removing useless symbols from CFGs: how order of removing non-reachable and non-generating symbols matter. Notes (not submitted)
Sep 11 More on removing useless symbols from CFGs. Removing unit productions from CFGs and examples. Notes (not submitted)
Sep 22 Summary of CFG simplifications. Chomsky-Normal Form (CNF) grammar: implications in terms of height of parse trees and length of derived string. Pumping Lemma (PL) for CFLs. Notes (not submitted)
Sep 23 More on PL for CFLs. Proving languages non-context-free using PL. Example of a non-CFL that satisfies PL. Introduction to Ogden's Lemma (OL) Notes (not submitted)
Sep 24 More on OL. Example of language that violates OL but satisfies PL. Closure of CFLs under union, concatenation, Kleene star, substitution, homomorphism. Non-closure under complementation and intersection. Push-down Automata (PDA). Notes (not submitted)
Sep 25 More on PDAs: basics, notation. Languages accepted by final state and by empty stack. Equivalence of acceptance by final state and by empty stack. Notes (not submitted)
Oct 11 More on equivalence of PDAs accepting by final state and by empty stack. Equivalence of CFGs and PDAs: constructing one from the other. Notes (not submitted)
Oct 12 Non-determinism in PDAs, non-equivalence of NPDAs and DPDAs. Closure properties of CFLs: intersection with regular languages, substitution, homomorphism, inverse homomorphism. Non-closure under intersection. Decision algorithms for CFLs: deciding emptiness, universality, finiteness of the language of a grammer. Deciding if a given string is in the language of a grammar. Notes (not submitted)
Oct 13 Introduction to Turing Machines (TM): definition, example, acceptance by final state, instantaneous descriptions (ID), converting a DFA into an equivalent TM. Notes (not submitted)
Oct 14 Equivalence of TM acceptance by halting and by final state. Transforming example TMs that accept by one criterion to TMs that accept by the other criterion. Notes (not submitted)
Oct 16 Embellishing TMs: multi-track tape, composite states, multiple tapes, single tape with mutliple heads. Proof that each of these TMs are no more powerful than the basic TM model. Examples. Notes (not submitted)
Oct 20 TMs with semi-infinite tape as equivalent to those with doubly-infinite tape. Equivalence of non-deterministic TMs and deterministic TMs. Equivalence of a Random Acces Memory machine and von Neumann computer and basic TM model. Notes (not submitted)
Oct 27 Building more complex TMs using macros. Flow-chart notation for combining simple TMs into more complex TMs. Example: building a TM to compute n^2 from n using unary notation. Notes (not submitted)
Oct 28 Using macros and flow-chart notation to construct TMs for computing the square of a number, adding two numbers, multiplying two numbers, raising one number to the power of the other, finding the quotient and remainder on dividing one number by another, finding the square root of a number, finding the fifth root of a number, etc. Overview of how a pseudocode for solving a problem can be translated into a TM using the flow chart notation and TM macros. Notes (not submitted)
Oct 31 DFAs with 2 stacks as equivalent to TMs. Counter machines: DFAs with counters. Equivalence of a TM to a 3 counter machine. Notes (not submitted)
Nov 3 Reducing a 3 counter machine to a 2 counter machine. Equivalence of DFA with 2 stacks, DFA with 2 counters and TMs. Recursively enumerable and recursive languages: basic definitions. Notes (not submitted)
Nov 4 Computational equivalence of a problem and its corresponding decision problem equivalent. Algorithms and procedures as recognizers of recursive and recursively enumerable languages. Notes (not submitted)
Nov 6 More on computational equivalence of a problem (e.g. shortest s-t path in a graph) and the corresponding decision problem. Recursively enumerable languages as languages whose strings can be enumerated by a TM. Recursive languages as languages whose strings can be enumerated in lexicographic order. Recursive languages and their importance. Properties of recursively enumerable and recursive languages and their complements. Encoding Turing Machines as integers. Notes (not submitted)
Nov 10 More on encoding TMs as integers. Proving that the diagonalization language is not recursively enumerable. Universal language: proving that it is not recursive. Undecidability of the halting problem. Notes (not submitted)
Nov 11 Reduction between problems. Proving problems undecidable by reduction from known undecidable problems. Post's Correspondence Problem (PCP), modified PCP (MPCP) and undecidability of PCP. Notes (not submitted)
Nov 12 Example of reduction of Halting Problem to MPCP. Using PCP to show that following properties of context-free languages are undecidable: emptiness of intersection of two CFLs, universality of a CFL, ambiguity of a CFG, regularity of the intersection of two CFLS. Notes (not submitted)
Nov 13 Trivial and non-trivial properties of recursively enumerable languages. Rice's Theorem, its proof idea and its implications. Notes (not submitted)
Nov 17 A host of undecidable problems: consequences of Rice's Theorem and undecidability of PCP. Computations with oracles: undecidable problems that are harder than other undecidable problems. Notes (not submitted)
Nov 18 Hierarchy of undecidable problems and its implications. Cocke-Younger-Kasami algorithm for checking membership of a string in a CFL. Notes (not submitted)