Theory of Computation

  • Credit points: 4 L[3] -T[0] – P[0] : 3 Credits : 3 Hours
  • Session: 4
  • Routine:
    1. Monday: 10.30AM – 11.30AM (Seminar Hall)
    2. Tuesday: 4.30PM – 5.30PM (Smart Class Room)
    3. Wednesday: 9.10AM – 10.10AM (Smart Class Room)
    4. Friday: 9.10AM – 10.10AM (Smart Class Room)

    • Attention: Students having attendance below 75% will not be allowed to appear in Semester Exam.

  • Course description:
  • Course objectives:
    1. Demonstrate understanding of the core concepts in automata theory and formal languages.
    2. Identify different formal languages and their relationships.
    3. Classify and construct grammars for different languages and vice-versa.
    4. Apply concepts to build finite automata, push down automata and Turing machine.
    5. Analyse various concepts of undecidability and computation functions for problem solving situations.
  • Syllabus:
    1. Alphabet, languages and grammars.
    2. Production rules and derivation of languages.
    3. Chomsky hierarchy of languages.
    4. Regular grammars, regular expressions and finite automata (deterministic and nondeterministic).
    5. Closure and decision properties of regular sets. Pumping lemma of regular sets.
    6. Minimization of finite automata.
    7. Left and right linear grammars.
    8. Context free grammars and pushdown automata.
    9. Chomsky and Griebach normal forms. Parse trees, Cook, Younger, Kasami, and Early's parsing algorithms.
    10. Ambiguity and properties of context free languages.
    11. Pumping lemma, Ogden's lemma, Parikh's theorem.
    12. Deterministic pushdown automata, closure properties of deterministic context free languages.
    13. Turing machines and variation of Turing machine model, Turing computability, Type 0 languages.
    14. Linear bounded automata and context sensitive languages.
    15. Primitive recursive functions. Cantor and Godel numbering.
    16. Ackermann's function, mu-recursive functions, recursiveness of Ackermann and Turing computable functions.
    17. Church Turing hypothesis.
    18. Recursive and recursively enumerable sets.
    19. Universal Turing machine and undecidable problems.
    20. Undecidability of post correspondence problem.
    21. Valid and invalid computations of Turing machines and some undecidable properties of context free language problems.
  • Recommended books:
    1. Buchi A, Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions, Springer-Verlag.
    2. H. R. Lewis and C. H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall, Englewood Cliffs.
    3. F. Hennie: Introduction to Computability, Addison Wesley Publ., New York.
  • Other resources:
    1. J. E. Hopcroft and J. D Ullman: Introduction to Automata Theory, Languages and Computation, Addison Wesley Publ., New York.
    2. Michael Sipser: Introduction to the Theory of Computation, 3E, Cengage Publisher, India
    3. Martin J C, Introduction to Languages and the Theory of Computation, McGraw-Hill International Edition.
    4. Mishra, K. L. P., & Chandrasekaran, N. (2006). Theory of computer science: automata, languages and computation. PHI Learning Pvt. Ltd.