COURSE SUMMARY
Course Title: 
Theory of Computation
Course Code: 
15CSE303
Year Taught: 
2015
2016
2017
2018
Semester: 
5
Degree: 
Undergraduate (UG)
School: 
School of Engineering
Campus: 
Bengaluru
Chennai
Coimbatore
Amritapuri

'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.