Automata and Computability
                      --------------------------

Instructor: Paritosh Pandya (A249, Phone 2551)
Venue and Date: Monday and Wednesdays From 3:00-5:00 p.m.
                A212 Lecture Room.

** Each Lecture is a 2 hour double lecture.

Contents
========

Lecture 1: 
Introduction to computablity.
Langauges and language recognition problem.
Finite state automata 1: DFA, NFA,
Reduction from NFA to DFA,

Lecture 2:
NFA-lambda, Reduction from NFA-lambda to NFA,
Regular Expressions, Reduction from  RegExp and NFA-lambda.


Lecture 3:
Reduction from DFA to RegExp,
Closure properties of Regular langauges,
Complexity of closure operations, 

Lecture 4:
Pumping Lemma, 
Ultimately periodic sets,
Decision problems for regular langauges,
Moore and Meely Machines

Lecture 5:
Myhill-Nerode Theorem,

Lecture 6:
Minimization of DFA,
Axiomatizing Equality of Regular Expressions,
Advanced topics: Extended regular expressions, star-height problems

Lecture 7:
Collapsing non-deterministic automata: Strong bisimilarity.

Lecture 8:
Alternating Finite State Automata and system of equations.
Applications of Finite State Automata
Implementation Issues

Lecture 9: 
Context Free Grammars: Derivations, Parse-trees, Ambiguous Grammars,
Normal Forms.

Lecture 10: Pushdown automata, Equivalence of PDA and CFLs.

Lecture 11:
Properties of CFLs: Pumping Lemma, Closure properties.

Extra Lecture 12:
Introduction to Logic and Program Verification (Hoare logic)

Lecture 13:
Notions of Computability and Decidability, Turing Machines,
Examples.

Lecture 14:
Robustness of TMs (Multitrack, Multitape, k-dimentional,
nondeterministic TMs and their equivalence to basic TM).
Two stack Machine, Counter Machine and their equivalence to TM.
RE and Recursive sets, TM as generator.

Lecture 15: Relationship between RE, Non-RE and REC languages. Closure
properties.
Coding and Enumerating Turing Machines, Universal TM,
Undecidability of Halting Problem.

Lecture 16: More Undecidable problems, Rice's theorem,
Post Correspondence Problem

Lecture 17-18: Chomsky Hierarchy

Lecture 19: Godels mu-Recusive Functions 

Lecture 20: Deterministic CFL and parsing:
theory of LR(0) parsing.

---------- TO BE DONE -----------

Lectures 21-23: Basic Complexity Theory 
Lecturer Jaikumar Radhakrishnan.
Complexity classes, NP-completeness, Space Hierarchy,
Gap and Speedup Theorems, Savitch's Theorem.

Textbooks:
----------

Hopcroft, Ullman, Introduction to Automata Theory, 
Languages and Computation, Special Student Edition,
Narosa Publishing House, India, 1987.

Dexter Kozen, Automata and Computability, Springer-Verlag.