IOE Syllabus of Theory Of Computation (TOC)

Theory of Computation (Subject code: CT 502) was introduced in BE Computer IOE Syllabus with the objective of providing understanding of theory of automata, formal languages, turing machines and computational complexity to students. Thee course is included in third year – first part of BCT and has no lab practicals but has 1 tutorial. The following syllabus is based on latest syllabus of IOE and also has marking scheme of each chapter and recommended books. We also have: Theory of Computation (TOC) IOE BCT Notes with Tutorial and Solution.

1. Introduction (4 hours)
   1. Set, relation, function, Proof techniques
   2. Alphabets, language, regular expression
2. Finite Automata (12 hours)
   1. Deterministic Finite Automata
   2. Non‐Deterministic Finite Automata
   3. Equivalence of regular language and finite automata
   4. Regular language, properties of regular language
   5. Pumping lemma for regular language
   6. Decision algorithms for regular languages
3. Context free language (12 hours)
   1. Context free grammar
   2. Derivative trees, simplification of context free grammar
   3. Chomsky normal form
   4. Push down automata
   5. Equivalence of context free language and push down automata
   6. Pumping lemma for context free language
   7. Properties of context free language
   8. Decision algorithms for context free language
4. Turing machine (10 hours)
   1. Definition of Turing machine, notation for Turing machine
   2. Computing with Turing machine
   3. Extensions of Turing machine
   4. Unrestricted grammar. (PDF – cs.tau.ac.il)
   5. Recursive function theory
5. Undecidability (5 hours)
   1. The Church‐Turing thesis
   2. Halting Problem, Universal Turing machine
   3. Undecidable problems about Turing machines, grammars
   4. Properties of Recursive, Recursively enumerable languages.
6. Computational Complexity (2 hours)
   1. Class P, Class NP, NP‐complete problems.

References

• H. R. Lewis, C. H. Papadimitriou, “Elements of theory of computation”, Pearson Education.
• Michael Sipser, “Introduction to the Theory of Computation”, Thomson Course Technology.

Evaluation Scheme

The questions will cover all the chapters of syllabus. The evaluation scheme will be as indicated in the table below:

Chapters Hours Marks distribution*

1 4 7

2 12 21

3 12 21

4 10 17

5 5 9

6 2 5

Total 45 80

* There could be a minor deviation in the marks distribution.