Automata and Languages: Chomsky hierarchy of languages, Introduction Finite Automata – Regular Expressions – Nondeterministic Finite Automata – equivalence of NFAs and DFAs – Minimization of DFA.

Regular Expressions – Non-Regular Languages – Pumping Lemma for regular languages.

Parse tree derivations (top-down and bottom-up) Context free languages –Chomsky normal form, GNF – Push Down Automata – Pumping lemma for context free language. CYK Algorithm, Deterministic CFLs. Ambiguous grammar, removing ambiguity, Computability Theory: Turing Machines – Non-deterministic Turing Machines –CSG, the Church Turing
thesis, decidability, halting problems, – PCP Computation histories – Reducibility.

Text Book

1. Michael Sipzer, “Introduction to the Theory of Computation”, Third Edition, Cengage Learning, 2012.

Reference

1. Linz P, “An Introduction to Formal Languages and Automata”, Fourth Edition, NarosaPublishing House, 2009
2. Martin and John, “Introduction to Languages and the Theory of Computation”, New York, McGraw Hill, 2002.
3. Garey, Michael and Johnson D S, “Computers and Intractability: A Guide to theTheory of NP-Completeness”, New York, W.H. Freeman and Company, First Edition, 1979.
4. J E Hopcroft, R Motwani and J D. Ullman, “Introduction to Automata Theory, Languages, and Computation”, Third Edition, Addison-Wesley, 2007.