Date  Topics  Student Notes 
Jul 22  Logistics. Motivation for studying theory of
computation. An example of a problem that cannot
be solved by a computer. 
Notes [PS] 
Jul 28  Alphabet, 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 29  Deterministic Finite Automata (DFA) basics
and examples. Acceptance of strings by DFA.
Language defined by a DFA 
Notes [PS] 
Jul 29  Nondeterministic Finite Automata (NFA) basics.
Acceptance condition of NFA. Language defined
by an NFA. 
Notes [PDF] 
Jul 30  NFAs continued. Equivalence of NFA and DFA.
Advantage of using NFAs. 
Notes (not submitted) 
Jul 31  Example 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 1  NFA 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 5  Regular expressions: syntax and semantics.
Constructing an NFA with epsilon transitions
from a regular expression. 
Notes (submitted, not verified) 
Aug 14  Constructing 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 18  Closure of regular sets under union, intersection,
complementation, finite number of Boolean operations.
Pumping Lemma for regular languages.
 Notes (not submitted) 
Aug 19  More on Pumping Lemma. Proving languages nonregular
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 21  Closure 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 25  More on inverse homomorphism. Proving nonregularity
of languages using closure results. Reasoning about
emptiness and finiteness of regular languages.
 Notes (not submitted) 
Aug 26  Quotients of regular languages with arbitrary
languages. Reasoning about the minimum number of
states needed to recognize a regular language.
 Notes (not submitted) 
Aug 28  The beauty of MyhillNerode Theorem. Proving
languages regular and nonregular using
MyhillNerode 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
nonterminals. 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
nonreachable and nongenerating 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. ChomskyNormal 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
noncontextfree using PL. Example of a nonCFL 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. Nonclosure under complementation and
intersection. Pushdown 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  Nondeterminism in PDAs, nonequivalence of NPDAs and DPDAs.
Closure properties of CFLs: intersection with regular
languages, substitution, homomorphism, inverse homomorphism.
Nonclosure 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: multitrack 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 semiinfinite tape as equivalent to those
with doublyinfinite tape. Equivalence of nondeterministic
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. Flowchart 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 flowchart 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 st 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
contextfree 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 nontrivial 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. CockeYoungerKasami algorithm
for checking membership of a string in a CFL. 
Notes (not submitted) 