CS-502 Automata Theory

Course Instructor: Dr. Abbas Kazim Zadi

Purpose of Course

Computer Science 502, deals with mathematical models of computation -- specifically, automata, which are idealized machines for manipulating strings of symbols, and grammars, which are collections of rules for transforming strings of symbols -- and with the characteristics of the classes of functions that can be defined and computed within these models. By abstracting from all attributes of actual computation that are not readily formalized, automata theorists have been able to establish quite general results about the capabilities and efficiencies of various computational methods. We shall study both the results that they have obtained and the mathematical techniques they use.

Objectives

Here is what each student in the course is expected to do:

• Read the textbook and the handouts carefully, learn the ideas, propositions, proofs, and techniques that are presented in them, and submit solutions to assigned exercises requiring their application.

• Prepare for and attend the sessions of the class. I strongly encourage each of you keep a notebook for summaries of and additions to the textbook, handouts, and discussions, and for questions raised by your reading and reflection.

• Take and pass two examinations -- one at mid-semester, the other at the end of the semester -- over the subjects that the course deals with.