Instructor:

K. R. Riggs, Ph.D.

Office: Banneker Tech Bldg. A, 213

Phone: 412-7351

E-mail: riggs@cis.famu.edu

WWW site: www.cis.famu.edu/~riggs (q.v. for class details as we go)

Office Hours: T-R 3:00-5:00, W 5:00-6:00 and by appointment

Text:

Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Co., 1997

Description:

COT5310 Theory of Programming Languages and Automata Prereq: COT3101, COT4210
Gives a formal background in computing theory and programming languages including the basis of machines and programming. Logical network and switching theory sequential theory and automata, and Turing machines and computability. Foundations of au tomata, formal languages of recursion theory.

Goals:

1. (General) Develop facility with formal proofs, objects and methods.
2. Develop facility with finite automata and context free grammars.
3. Understand how Turing Machines define what is / is not computable.
4. Learn what intractable problems are, what they mean and how they can be recognized.

Class Details:

Approximate Calendar

C0) Introduction	C3) Church Turing Thesis	C7) Time Complexity
C1) Regular Languages	C4) Decidability	C8) Space Complexity
C2) Context Free Languages	C5) Reducibility	C9) Intractability
Review & ??	Review & ??	Review & ??
Exam 1	Exam 2	Exam 3

• Assignments may include programming or using web-based tools for constructing machines.
• Last exam will be during the Final Exam Week.

Grading:

Exams: 3 75%

Assignments 25%

Scale: A-90%, B-80%, C-70%, D-60%, <60%-F

Policies:

• All work is individual. Violations will result in dismissal from the course with a grade of F.
• Attendance is required and includes attention, participation, proper behavior, etc.
• Assignments are not accepted late. They may be accepted early, if need is established.
• Exams are not made up after the fact. Missed exams are scored 0. Excused absences, with documentation, will be handled according to the case.