Prerequisites:Math 3336 and COSC 2320. Math 3336 will be strictly enforced.

Textbook

• Introduction to the Theory of Computation by M. Sipser, PWS Publishing Co.

References

• Elements of the Theory of Computation by H. Lewis and C. Papadimitriou, Prentice Hall,

First and second editions.

• Introduction to Automata Theory, Languages and Computation by J. Hopcroft, R. Motwani

and J. Ullman, Addison-Wesley, 2001.

Goals

• To provide computer science students with a broad understanding of various models of com

putation, several different characterizations of the power of each model, and the relative power

of the models. Students are taught what can and what cannot be computed even by idealized

computing devices. They are exposed to essential computational paradigms in a rigorous way.

Topics

• Finite Automata and Regular languages.

• Pushdown Automata and Context-free languages.

• Turing Machines.

• Church's thesis, Grammars, Universal Turing Machines.

• The Halting Problem, Turing-Acceptability, Turing Decidability, and Unsolvable problems

about Turing machines.

• Cardinality of sets, Proof techniques, and basic de¯nitions.

Instructor:

Rakesh Verma.

Office 532 PGH, Ph: 743-3348.

Office Hours for Fall 04: TuTh: 5.30-6.25pm (or by appt.)

TA: TBA

Academic Honesty Policy:Assistance of or Collaboration with any animate or inani

mate object (except the instructor and the TAs) is completely disallowed on all exams;

any violation will be severely penalized with the minimum penalty on FIRST violation

being an F grade.

Grading: Homeworks 10%, Exam 1 24%, Exam 2 30%, Final 36%