Theory of Computation

Code: MA514 | L-T-P-C: 3-1-0-8

Prerequistes: MA 501 Discrete Mathematics

Alphabets, languages, grammars; Finite automata, regular languages, regular expressions; Context-free languages, pushdown automata, DCFLs; Context sensitive languages, linear bounded automata; Turing machines, recursively enumerable languages; Operations on formal languages and their properties; Chomsky hierarchy; Decision questions on languages; NP-Completeness.

Texts:

1. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004.
2. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981.

References:

1. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.
2. Peter Linz, An Introduction to Formal Languages and Automata, Narosa, 2007.
3. D. C. Kozen, Automata and Computability, Springer-Verlag, 1997.
4. D. S. Garey and G. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.