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 | Non-deterministic 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 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 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 non-regularity
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 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) |