Theory of Computation

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

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:

• J. E. Hopcroft, Rajeev Motwani and  J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Third Edition,  Pearson Education India, 2008.
• H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, Pearson Education, 1998.

 

References:

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