Course Number and Title: CS 5313, Formal Language Theory
Meeting Time: 3:30-6:10 M Meeting Place: MS 445

Instructor: M. Samadzadeh Office: MS 215 Phone: 744-5668
Office Hours: 2:00 - 3:00 MWF, or by appointment

Graduate Assistant: Arif Muljadi Office: MS 316C Phone: 744-7277
Office Hours: 11:00 - 13:00 M, 2:30 - 4:30 Tu, or by appointment

Prerequisite: CS 3613 Theoretical Foundations of Computing

Required Text: A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Volume I: Parsing, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1972.

Optional/Recommended Texts, etc.:
1- J. G. Brookshear, Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc., 1989.
2- J. C. Cleaveland and R. C. Uzgalis, Grammars and Programming Languages, Elsevier North Holland, Inc., 1977.
3- V. Drobot, Formal Languages and Automata Theory, Computer Science Press, Inc., 1989.
4- J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Company, Inc., Reading, MA, 1979.
5- M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Publishing Company, Inc., Reading, MA, 1978.
6- Peter Linz, An Introduction to Formal Languages and Automata, D. C. Heath and Company, Lexington, Massachusetts, 1990.
7- Alexander Meduna, Formal Language Theory, Harper Collins Publishers, Glenview, Illinois, 1995.
8- J. E. Pin, Varieties of Formal Languages, Plenum Publishing Corporation, 1986.
9- Arto Salomaa, Jewels of Formal Language Theory, Computer Science Press, Inc., 1981.
10- T. A. Sudkamp. Languages and Machines, Addison-Wesley Publishing Company, Inc., Reading, MA, 1988.
11- Various Periodical Articles and Technical Publications.

Course Description: Formal language theory applied to procedure-oriented languages. Applications of finite state algorithms to lexical analysis. Chomsky hierarchy of languages. Generation, recognition, and closure properties of languages.

Grading: HWs and Prog. Assignments 30%
Examinations 20% each (Sept. 25 and Oct. 30)
Final Examination (comp.) 30% (Dec. 11, 3:30-5:20 PM)

Letter Grades: [90-100] A
[80-90) B (The instructor reserves the right to
[70-80) C adjust the grading scale provided that
[60-70) D it does not lower any student's grade.)
[0-60) F

Note: Late Homeworks will not be accepted. Late Program penalty is 10% a day. No make-up tests will be given unless there is an extraordinary situation.

Policy on Attendance: Attendance is required but not monitored. Students are responsible for all material discussed in class.

Collaboration Policy for CS 5313

Homework: Discussion of any kind is allowed. After discussion, each student must write up his/her own solution. Copying another student's work is not allowed. Giving another student your work is considered cheating as well.

Examinations: No discussion of any kind (except with the instructor) is allowed. No access to any type of written material is allowed.

Students who do not comply with the described collaboration policy will receive a grade of F in the course. Furthermore, the case will be reported to the University Officials.