MET CS 662
Home ] Assignments ] Outline ]





The goal of this course is to provide the student with a solid knowledge of the fundamental concepts and methods of the theory of computation as well as to outline modern research directions. Three different approaches for capturing the idea of computing in a formal mathematical way will be discussed finite state machines, grammars and recursive functions. At the end of the course students are expected to be able to interpret relate and apply the basic concepts of the theory of computation to problems from different areas of computer science.

Course Objectives

  • Apply the algebra of theoretical machines to computing problems

  • Possess knowledge of non-determinism in computational models.

  • Remove nondeterminism from simple models when it is possible.

  • Understand the basic problems of computability, decidability and the halting problem as well as the relationships among them.

  • Apply the concept of a Turing machine to the decidability problem where possible.

  • Understand the Church-Turing Thesis and its significance in computer science.

  • Have a working knowledge of the Chomsky hierarchy of languages.

  • Relate theoretical computer science topics to programming languages and other recursively enumerable sets.


  • Discrete Mathematics course ( MET CS248 or equivalent.)

  • Introductory computer programming class


  • P. Linz "An Introduction to Formal Languages and Automata" 3rd or 4th edition, D.C. Heath and Co. (2001 - 2006)


  • Midterm            35%   (Date will be announced)

  • Final Exam        35%   (Date will be announced)

  • Assignments      30%     


  • 1- H. R. Lewis, C. H. Papadimitriou "Elements of the Theory of Computation" Prentice Hall, 1981.

  • 2- J.E. Hopcroft, "Introduction to Automata Theory, Languages and Computations" Addison Wesley, 1979.

Course Outline

Assignments (3rd ed)

Assignments (4rd ed)