Michigan State University

Department of Computer Science

Course Information

CPS 360: Automata and Formal Language Theory

Summer, 1998

Instructor: Travis Doom, Ph.D. Candidate, Computer Science Department
Office: 3358 Engineering Building (353-8669)
Office hours: MWF 2:30-3:00, TR 2:00-3:00, others by appointment
Email: doom@cps.msu.edu
Web page: http://www.cps.msu.edu/~doom

Meeting Time: MWF 12:40-2:30, 2320 EB (5/18/98 ū 7/02/98)
There will be a 10 min. class break, usually beginning between 1:30 and 1:45

Textbook: Martin, John (1997). ``Introduction to Languages and the Theory of Computation,'' Second Edition. New York: McGraw-Hill.

Objectives: This course has two primary objectives. The first is content-based. We hope to teach students the fundamental concepts of formal language theory and computability theory. In formal language theory, we study languages from several different viewpoints and prove general properties about various types of formal languages. This is a critical area of study as we need to understand what types of languages computers will be able to understand. In computability theory, we construct general models of computation and explore the fundamental capabilities and limitations of digital computers. This is a critical field of study as we learn there are important practical problems we can never expect computers to solve for us.

The second objective is skill-based. In CPS 260, you are taught some basic skills such as how to prove theorems. In this course, we hope to teach you how to apply these skills in "real-life" situations. Furthermore, we hope to teach you the importance of a careful, methodical approach to the construction of proofs and algorithms.

Clustering of grades may cause the thresholds to be lowered; they will not be raised.

In-class participation and homework presentation: Daily homework will be assigned, but will not be collected. Students will be asked to participate in the learning process by periodically presenting the solutions to selected homework problems to the class. We will often consider very difficult problems in this course. Students who make a reasonable effort to present a difficult problem will receive full credit, regardless of correctness.

Examinations and Quizzes: Examinations will be closed-book but one sheet of 8.5 x 11" paper of notes (double-sided) may be brought. The mid-term examination (6/12/98) and final examination (7/1/98) will occur during the normally scheduled class time at the normally scheduled location. A short in-class quiz will occur on each Friday on which an exam is not scheduled (5/22/98, 5/29/98, 6/5/98, 6/19/98, and 6/26/98).

Absences: Any extenuating circumstances which impact on your participation in the course should be discussed with me as soon as those circumstances are known. Make-ups for graded activities may be arranged if a studentĘs absence is caused by documented illness or personal emergency. A written explanation (including supporting documentation) must be submitted; if the explanation is acceptable, an alternative to the graded activity will be arranged. Whenever possible, make-up arrangements must be completed prior to the scheduled activity.

Feedback sheets: Feedback sheets may be distributed by the instructor during class time. Your opinion will be solicited via a non-technical question regarding some aspect of the course. Anyone writing their name at the top of the page and answering the question will get an extra credit of 2 points. Feel free to provide additional feedback at any time. It is likely that I will not teach this material in a way which is best for all students. If you have any suggestions, please discuss them with me. This is your education, make the most of it.

Classroom Behavior: Summer courses tend to be intense and fast-paced. Come to class on time. The first 5 minutes of each class sets the direction and tone for the day. If you come in late, things may make less sense to you. If you miss a day, you are responsible for the material presented. DonĘt sleep, read the newspaper or do crossword puzzles. Once class begins, I expect students to help provide a productive learning environment for all by paying attention and asking questions. The material in this course is non-trivial; if you have a question, others are likely to be confused as well. Do not be afraid to "slow the course down". If I feel that we reach a point at which the class as a whole must move on, I will say so.

Collaboration: Students are encouraged to get together in small study groups to discuss the course topics and homework problems. Small group discussion and collaboration is a vital aid to mastering the concepts presented in this course. The class as a whole will often collaborate on homework problems presented in class. Only during quizzes and examinations is collaboration prohibited. Formal in-class testing is subject to the standard guidelines for academic honesty ( http://www.msu.edu/unit/ombud/dishonesty.htm).

Additional Information: Information regarding course readings, homework assignments, and syllabus updates will be available via World Wide Web. Although this information is provided primarily for the convenience of students who are unable to attend a lecture, all students are responsible for reading this material on a weekly basis. Students that do not have active CPS accounts or are otherwise unable to access the course WWW page should contact me.