CPTR 324 Automata, Formal Languages, and Computablility


January 7, 2008


Instructor: Dr. Eileen M. Peluso, D307 Academic Center, Extension 4135

Email: pelusoem@lycoming.edu

Office hours: to be announced . . . on my web page www.lycoming.edu/~pelusoem.


Objective: The goal of this course is to introduce students to the notion of computability and the theoretical limits of computation. By investigating various types of "machines" (also referred to as automata) and their equivalent formal language counterparts, the students will discover the computational power and limitations associated with each. Specifically, the students will develop a working knowledge of finite state machines, push-down automata, and Turing machines, the latter being computationally equivalent to the modern day computer.


Text: Michael Sipser, Introduction to the Theory of Computation, 2nd edition, Thomson Course Technology, 2006.


Other course materials: JFLAP automaton simulator, freely downloadable from www.jflap.org.



         Weekly Take-home Quizzes: 50%

         Exams(2): 30% (tentatively scheduled for Wednesday, February 13th and Wednesday, March 19th)

         Comprehensive Final: 20%


Grade scale: If you earn the following average, you will receive at least the grade indicated.

         90.0 or above A

         85.0 89.9 A-

         80.0 84.9 B+

         75.0 79.9 B

         70.0 74.9 B-

         65.0 69.9 C+

         60.0 64.9 C

         55.0 59.9 C-

         50.0 54.9 D

         below 50.0 F



1.        Students will not be excused from exams unless

         they are ill and have been to the infirmary or have seen a doctor, or

         they have an emergency situation and have received exemption from the dean.

It is wise to contact me before missing an exam or quiz. Any tests missed will result in a grade of zero unless arrangements for a make-up are made within 48 hours.

2.        Class attendance is important and expected. If in some emergency circumstance (such as illness and inclement weather) you are not able to attend class, inform the instructor as soon as possible. It is the student's responsibility to obtain details about the missed work, announcements and any information disseminated during the missed classes.

3.        Take-home quizzes will be given weekly on Fridays, due the following Friday unless stated otherwise. Each will consist of approximately 3 to 5 questions/problems that are designed to solidify your understanding of the material presented in the text and lectures.

4.        Academic Dishonesty: Discussions with other students about take-home quizzes are encouraged, however completing take-home quizzes as a group activity is not allowed. Obviously, you should never have in your possession or have access to (in paper or electronic form) a copy of someone else's take-home quiz. As a general rule of thumb: The difference between sharing ideas and plagiarism will be determined by the instructor as follows: if you cannot discuss, expound upon, and justify what you have submitted, then you have plagiarized.