CPTR 324 Automata,
Formal Languages, and Computablility

Syllabus

January 7, 2008

**Instructor:** Dr. Eileen M. Peluso, D307

**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*,
2^{nd} edition, Thomson Course Technology, 2006.

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

**Grading:**

· Weekly Take-home Quizzes: 50%

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

· 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

**Remarks:**

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.