| Course Code: CS205 Course Name: Formal Languages, Automata Theory and Computation Prerequisites: NIL Syllabus: 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. Texts: 1. J. Hopcroft, J. D. Ullman, R. Motwani, Introduction to Automata Theory, Languages and Computation, 3rd Ed., Pearson, 2008. References: 1. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981. 2. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004. 3. C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1994. 4. D. C. Kozen, Automata and computability, Springer, 1997. 5. D. S. Garey and G Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. 6. J. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd Ed., Narosa, 1995. |