Back close
Admissions

Course Detail

Course Name Theory of Computation
Course Code 15CSE303
Program B. Tech. in Computer Science and Engineering (CSE)
Semester Five
Year Taught 2019

Syllabus

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.

Text Books

  • Linz P., “An Introduction to Formal Languages and Automata”, Fourth Edition, Narosa Publishing House, 2009

Resources

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

DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.

Admissions Apply Now