Office of Academic Affairs
Indian Institute of Science Education and Research Berhampur

Computer and Data Sciences

CDS 303: Theory of Computation

Course Contents:

Module-1:

Introduction, definition, concept of sequential circuits, state table & state assignments, concept of synchronous, asynchronous and linear sequential machines. Basic definition, mathematical representation, Moore versus Mealy m/c, capability & limitations of FSM, state equivalence & minimization, machine equivalence, incompletely specified machines, merger graph & compatibility graph, merger table, Finite memory, definite, information loss less & inverse machines: testing table & testing graph.

Module-2:

FSA, NFSA, NFSA with € moves, Regular expressions, Equivalence of regular expression and FSA, Equivalence of type 3 grammars and FSA, Pumping lemma, Closure and decidability results, Myhill-Nerode theorem, Minimization.

Module-3:

Grammars, Languages generated, Chomsky Hierarchy, CFG, Ambiguity, Reduced grammars, Normal forms. Pumping lemma & its application, closure properties. Context Free Grammars: Introduction, definition, derivation trees, simplification, CNF & GNF.

Module-4:

Pushdown Automata, Acceptance by final state and empty stack, Equivalence to CFG, Deterministic PDA.

Module-5:

Turing Machines - Construction, Techniques of TM construction, TM as acceptor and i/o device, Problems. Generalized and restricted versions.

Module-6:

Halting problems - Universal TM-recursive and recursively enumerable sets - Decidability - Rice’s Theorem, PCP.

Text Books:

  • J. E. Hopcroft, J. D. Ullman and R. Motwani: Introduction to Automata Theory, Languages and Computation, Addison- Wesley, California, 2001.
  • M. Sipser: Introduction to the Theory of Computation, PWS Pub. Co., New York, 1999.
  • Peter Linz, An Introduction to Formal Languages and Automata.
  • M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to The Theory of NP-Completeness, Freeman, New York, 1979.
  • M. D. Davis, R. Sigal and E. J. Weyuker: Complexity, Computability and Languages, Academic Press, New York, 1994.
  • N. J. Cutland: Computability: An Introduction to Recursive Function Theory, Cambridge University Press, London, 1980.
    • Previous Back to Course List Next
    Office of Academic Affairs