Formal Languages & Automata Theory

Code: MA351 | L-T-P-C: 3-0-0-6

Alphabets, languages; Regular Languages: various types of finite automata and their equivalences thereof, minimization of finite automata, Myhill-Nerode theorem, regular expressions, regular grammars, closure properties of regular languages, pumping lemma, algorithmic properties of regular languages; Context-free languages: context-free grammars, derivation trees, ambiguous grammars, inherently ambiguous languages, Chomsky and Greibach normal form, nondeterministic and deterministic pushdown automata, Top-down and Bottom-up parsing LL(k) and LALR grammars, pumping lemma and Ogden's lemma, closure and algorithmic properties of context-free languages; Context sensitive languages: context sensitive grammars, linear bounded automata; Turing machines: recursively enumerable languages, unrestricted grammars, variants of Turing machines and equivalence thereof.

Texts:

1. J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Pearson Education India, 2001.
2. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall of India, 1997.

References:

1. M. Sipser, Introduction to the Theory of Computation, Thomson Asia, 1997.
2. D. C. Kozen, Automata and Computability, Springer-Verlag, 1997.
3. D. I. A. Cohen, Introduction to Computer Theory, John Wiley, 1997.