| Course Code: CS2003 Course Name: Formal Languages and Automata Theory Prerequisites: NIL Syllabus: Introduction: Alphabets, strings, languages, and operations on languages. Grammars and their classification; Regular languages: regular expressions, finite automata (DFA, NFA, ?-NFA), equivalence and minimization, closure properties, pumping lemma, Myhill-Nerode theorem, Algebraic perspective of regular languages: syntactic congruence and introduction to syntactic monoids, Introduction to automata learning via queries - the basic idea of Angluin `s L* algorithm; Logical characterization of regular languages: strings as logical structures, introduction to first-order logic on words, and equivalence between automata and logical definability (MSO); Context-free languages: context-free grammars, pushdown automata, normal forms (CNF), closure properties, pumping lemma for CFLs, Parikh image and Parikh `s theorem; Computability and complexity: recursive and recursively enumerable languages, Turing machines and unrestricted grammars, operations on languages and their properties, Chomsky hierarchy, decision problems on languages, reductions, Church-Turing thesis, undecidability. Introduction to complexity theory: classes P and NP, NP-completeness, and the Cook-Levin theorem. Texts: 1. J. Hopcroft, J. D. Ullman, R. Motwani, Introduction to Automata Theory, Languages and Computation, 3rd Ed., Pearson, 2008. 2. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004. 3. E. Gradel, W. Thomas, and T. Wilke (eds.), Automata, Logics, and Infinite Games: A Guide to Current Research, Lecture Notes in Computer Science, Vol. 2500, Springer, Berlin, Heidelberg, 2002. 4. D. C. Kozen, Automata and computability, Springer, 1997. 5. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981. 6. D. Angluin, Learning Regular Sets from Queries and Counterexamples, Information and Computation, Vol. 75, No. 2, pp. 87-106, 1987. (For Automata Learning only) 7. W. Kuich, ``Parikh `s Theorem: A Simple and Direct Construction,`` arXiv preprint, arXiv:1006.3825, 2010. (For Parikh `s Theorem only) References: 1. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981. 2. C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994. 3. D. S. Garey and G Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. |