FMCS

E0 222 (AUG) 3:1 Formal Methods in Computer Science

Course Contents

Automata Theory, Finite automata and their use in modelling, Pushdown

automata, context free languages, Turing Machines, undecidability.

Complexity, Theory: Basic complexity classes, reductions, hardness and

completeness with emphasis on NP-completeness.

Hopcroft J.E. and Ullman, J.D., Introduction to Automata, Languages and

Computation, Addison Wesley, 1979.

Dexter Kozen: Automata and Computability, Springer, 1999.

H.R. Lewis and C.H. Papadimitriou: Elements of the Theory of Computation,

Prentice Hall, 1981.

C.H. Papadimitriou: Computational Complexity, Addison-Wesley, 1994.

The course is taught by

    Prof Deepak D'Souza