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.