CS 205	Formal Languages, Automata Theory and Computation	3-0-0-6
Pre-requisites : NIL Alphabets, languages, grammars. Regular languages: regular expressions, finite automata, linear grammars. Context-free languages: pushdown automata, context-free grammars. Recursive languages. Recursively enumerable languages: Turing machines, unrestricted grammars. Operations on formal languages and their properties. Chomsky hierarchy. Decision questions on languages. Church's thesis. Undecidability. NP completeness. Cook-Levin Theorem. Textbook: 1. J. Hopcroft, J. D. Ullman, R. Motwani, Introduction to Automata Theory, Languages and Computation, 3rd Ed., Pearson, 2008. References: 2. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981. 3. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004. 4. C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1994. 5. D. C. Kozen, Automata and computability, Springer, 1997. 6. D. S. Garey and G Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. 7. J. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd Ed., Narosa, 1995.