Theory of Computation

Code: MA351 | L-T-P-C: 4-0-0-8

Prerequisites: MA221 or equivalent

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; Decidability; Undecidability; Cook’s theorem.

Texts:

1. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1995.
2. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, Pearson Education, 1998.

References:

1. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004.
2. P. Linz, An Introduction to Formal Languages and Automata, Narosa, 2007.
3. D. C. Kozen, Automata and Computability, Springer, 1997.