Pre-requisites : CS202

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 and Computation, 2/e, Pearson Education, 2000.

References :
1. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004.

2. H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, Pearson Education Asia, 2001.

3. D. C. Kozen, Automata and Computability, Springer-Verlag, 1997.