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.

We're always listening.
Have something to say about this article? Find us on Facebook, Twitter or our LinkedIn.
Raju Dawadi
Raju Dawadi
Raju is currently actively involved in DevOps world and is focused on Container based architecture & CI/CD automation along with Linux administration. Want to discuss with him on any cool topics? Feel free to connect on twitter, linkedIn, facebook.

1 Comment

  1. […] The complete course content/syllabus with marking scheme of the subject can be accessed from Theory of Computation -TOC IOE Syllabus page. […]

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.