Back close
Admissions

Course Detail

Course Name Theory of Computation
Course Code 26CSC304
Program 5 Year Integrated M.Sc in Data Science
Semester 5
Credits 4
Campus Coimbatiore

Syllabus

Syllabus

Suggested lab exercises:

The lab exercises are implementing using JFLAP (Java Formal Languages and Automata Package) is a visual simulation tool that makes abstract ToC concepts practical and interactive. It is especially useful for students who find automata theory highly mathematical.

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,

Unit 4

Computability Theory: Turing Machines – Non-deterministic Turing Machines CSG, Undecidability – PCP Computation histories Reducibility.

Text Books / References

Text books

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

Reference Books

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

Introduction

This course provides an overview of the problems that can be solved by various kinds of abstract machines such as finite state machine, pushdown automata and Turing machine. It also deals with how efficiently problems can be solved on a model of computation, using an algorithm.

Objectives and Outcomes

Course Outcomes: After successful completion of the course, students will be able to

  1. Understand and apply the properties of formal languages
  2. Illustrate grammar and grammar transformations for formal languagesConstruct finite state machines
  3. Apply stack data structures for automata
  4. Design and develop computing devices such as Turing machines

CO-PO Mapping:

  PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 3 3 2 2                
CO2 2 2 2 2                
CO3 2 2 2 2                
CO4 2 2 2 2                
CO5 3 2 2 2                

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