| Date | Topics |
|---|
| Jul 22 | Logistics. Motivation for studying theory of
computation. Overview of simple proof techniques:
mathematical induction and generalization
to well ordered sets |
| Jul 23 | Proof techniques: generalized induction, method of
contradiction, diagonalization principle, pigeon-hole
principle. Notions of cardinality of sets and counting
arguments. |
| Jul 24 | More on counting arguments, infinities of different
orders. Finite, countably infinite and uncountable sets.
Notions of alphabet, strings, languages. Counting the
number of strings and languages. |
| Jul 29 | Why no computer can generate all languages from an alphabet
with only one symbol. Deterministic finite automata (DFA):
definitions, acceptance of strings, language of an automaton.
|
| Jul 30 | Notions of language acceptance and generation and their
relation to computing functions of integers, functions
computable by finite automata
|
| Aug 1 | More on how to compute functions using computational models
for generating/accepting languages. Notion of non-deterministic
finite automata (NFA). Equivalence of computational power
of DFA and NFA.
|
| Aug 5 | Subset construction for showing equivalence of DFA and NFA,
examples. NFAs with epsilon transitions.
|
| Aug 6 | Equivalence of NFAs with and without epsilon transitions.
Introduction to Regular Expressions
|
| Aug 7 | Regular Expressions: algebraic structure, descriptors of
sets of strings or languages. Operations on regular expressions
and corresponding set theoretic operations on languages.
Equivalence of regular expressions and finite automata:
converting a regular expression to an NFA with epsilon
|
| Aug 12 | Converting a DFA to an equivalent regular expression.
Complement, reverse of a regular language is regular
|
| Aug 13 | Pumping Lemma for regular languages, examples of languages
that can be proved non-regular using pumping lemma
|
| Aug 14 | More on pumping lemma. Closure of regular languages under
complement, union, intersection. Product automaton construction;
DFAs for languages obtained by set operations on regular languages.
Substitution of regular languages
|
| Aug 19 | Closure of regular languages under substitution, homomorphism,
inverse homomorphism; examples.
|
| Aug 20 | Closure of regular languages under quotient with regular and
non-regular languages. Introduction to Myhill-Nerode
Theorem: use in minimizing DFAs
|
| Aug 21 | More on Myhill-Nerode theorem and minimizing DFAs
|
| Sep 3 | Algorithm for minimizing DFAs, canonical (upto isomorphism) minimal
DFAs. Decision algorithms for regular languages: equality
of languages, language containment, emptiness checking, finiteness
checking.
|
| Sep 4 | Introduction to Context-Free Grammars (CFG) and Context-Free
Languages (CFL). Derivations: leftmost and rightmost; parse
trees.
|
Sep 4
(extra lecture) |
Equivalence of parse trees, leftmost and rightmost derivations.
Ambiguous grammars, removing ambiguity from simple grammars,
inherently ambiguous languages.
Introduction to Pushdown Automata (PDA) -- notions of acceptance
by final state and by empty stack
|
| Sep 9 | More on PDAs: epsilon transitions, non-deterministic and
deterministic PDAs. Instantaneous descriptions of a PDA.
Equivalence between PDAs accepting by null stack and
those accepting by final state.
|
| Sep 11 | Brush with determinstic PDAs (DPDA): languages accepted
by DPDAs by final state and by empty stack; relations
between them. Equivalence of CFGs and PDAs.
|
Sep 11
(extra lecture) | Equivalence of CFGs and PDAs: constructions
and proofs. Removing useless symbols, epsilon productions and
unit productions from arbitrary CFGs. Chomsky-Normal form for
CFGs.
|
| Sep 23 | Ogden's Lemma for CFLs |
| Sep 24 | Pumping Lemma and Ogden's Lemma for CFLs; closure
of CFLs under union, reversal; non-closure under
complementation, intersection |
| Sep 25 | Closure of CFLs under substitution, homomorphism,
inverse homomorphism; decision algorithms for CFLs:
emptiness, finiteness, membership |