Pre-requisites : CS203

Syllabus : Alphabets, Languages, Grammars. Finite automata: regular expressions, regular languages. Context free languages: pushdown automata, DCFLs, LL(k) and LALR grammars. Context sensitive languages: linear bounded automata. Turing machines: recursively enumerable languages. Operations on formal languages and their properties. Decision questions on languages, Undecidable problems.

Texts :
1. Hopcroft J.E, Ullman, J.D., Introduction to Automata Theory, Languages and Computation, Narosa, 1979.

2. Martin, J.C., Introduction to Languages and the Theory of Computation, McGraw-Hill International Editions, Computer Science Series, 1991.

References :
1. Buchi, A., Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions, Springer-Verlag, New York, 1989.

2. Lewis, H.R, Papadimitriou, C.H., Elements of the Theory of Computation, Prentice-Hall of India, New Jersey, 1981.

3. McNaughton, R., Elementary Computability, Formal Languages and Automata, Prentice-Hall, 1982.