Pre-requisites : CS202 or equivalent.

Syllabus :
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.

Texts :
1. J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages andComputation, 2nd Ed., Pearson Education, 2000.

References :
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, Pearson Education Asia, 2001.
3. D. C. Kozen, Automata and Computability, Springer-Verlag, 1997.