'Theory of Computation' is a course offered in the fifth semester of B. Tech. in Computer Science and Engineering program at School of Engineering, Amrita Vishwa Vidyapeetham.
Unit 1
Automata and Languages: Chomsky hierarchy of languages, Introduction Finite Automata - Regular Expressions - Nondeterministic Finite Automata - equivalence of NFAs and DFAs – Minimization of DFA.
Unit 2
Regular Expressions - Non-Regular Languages - Pumping Lemma for regular languages.
Unit 3
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, Undecidability - PCP Computation histories – Reducibility.
- Linz P., “An Introduction to Formal Languages and Automata”, Fourth Edition, Narosa Publishing House, 2009
- Michael Sipzer, “Introduction to the Theory of Computation”, Third Edition, Cengage Learning, 2012.
- Martin and John, “Introduction to Languages and the Theory of Computation”, New York, McGraw Hill, 2002.
- Garey, Michael and Johnson D. S., “Computers and Intractability: A Guide to the Theory of NP - Completeness”, New York, W. H. Freeman and Company, First Edition, 1979.
- J. E. Hopcroft, R. Motwani and J. D. Ullman, “Introduction to Automata Theory, Languages, and Computation”, Third Edition, Addison-Wesley, 2007.
