Binghamton University - Watson School
CS373 - AUTOMATA AND FORMAL LANGUAGES
DESCRIPTION - RULES – REQUIREMENTS
(SUBJECT TO REVISION)
January 21, 2003, updated: 2/11/03
INSTRUCTOR: Dr. Nicholas M. Guydosh
OFFICE: N7 CS Dept.
PHONE: Office: 777-4641, CS Dept. Secretary: 777-4802
E-mail:
listserve email address:
Website: http://www.cs.binghamton.edu/~guydosh/cs373/
LECTURES (Sect 90): MWF 10:50- 11:50AM, Room S2-260
LAB/DISCUSSION CLASS: Thuresdays, 1:15 – 2:40PM, Room SW331
OFFICE HOURS: Monday and Wednesday: 3:30 - 4:30PM, or by appointment office N7., CS Dept.
TA: Brett Bernstein
Email:
Office Hours: Tuesdays 1:15 to 2:15, In the Micro lab
COURSE DESCRIPTION: This course will provide a foundation to the “Theory of Computation”. The student will realize that the sometimes chaotic technology oriented world of computers has a very elegant mathematical basis to it. This basis is deeply rooted in mathematics developed before the days of modern computers. Our study will lead to some interesting implications concerning the theoretical limits of computing. On the practical side, this course is a background for a course on compilers. Topics covered in this course include: mathematical prerequisites, finite state machines (automata), concept of a language and grammars, deterministic and non-deterministic accepters, regular expressions and languages, context-free languages, normal/canonical forms, pushdown automata, Turing machines, context sensitive languages, recursive and recursively enumerable languages. Each of the various language classes above, will be approached from two points of view: a class of automata defining the language, and a class of grammars defining the language. This dual approach to defining languages, will finally lead to the Chomsky hierarchy of languages. We shall observe that the Turing Machine automata not only serves to define a language class, but it also is a mathematical model for computation itself and defines the theoretical limits of computation.
PREREQUISITES: MATH 314, Discrete Mathematics
CS 240, Data Structures
CS 210 logic design (coverage on state machines) is recommended
TEXT: Peter Linz, "An Introduction to Formal Languages and Automata", 3rd ed., Jones and Bartlett, 2001
COURSE REQUIREMENTS:
Home work/Quizzes...... 20 % of grade
Programming projects …...... 5 % of grade
Term Examination 1 ...... 25 % of grade
Term Examination 2 ...... 25 % of grade
Final Examination ...... … 25 % of grade
------
Total …...... 100%
GRADING RUBRIC: At the end of the semester, a raw average is computed using the weightings given in “Course Requirements” above. “Curving” adjustments, if any, are made on this average. Finally, letter grades are assigned using the following rubric:
90 through 94.9: A-, 95 through 100: A
80 through 83.3: B-, 83.4 through 86.6: B, 86.7 through 89.9: B+
70 through 73.3: C-, 73.4 through 76.6: C, 76.7 through 79.9: C+
60 through 69.9: D
Under 60: F
LAB/DISCUSSION GROUP SESSIONS:
The “Lab” or “Discussion Group” sessions will be used in this course this course. It will have the following objectives and guidelines:
- Additional discussion of the material covered by the lectures.
- The focus of the lab is on homework assignments, quizzes, and programming assignments.
- Discussion and help in the current homework and programming assignments.
- In general a quiz will be given related to the previous homework assignment. In order to do well on the quiz, you will have to do a conscientious job on the homework. The TA will give more details on the homework and quizzes.
- Java programming assignments on various topics in this course will be associated with this lab, and will be under the supervision of the TA
- The lab sessions will be conducted by the TA.
- Attendance is required.
ATTENDANCE AND OTHER GRADING FACTORS: Although lecture notes and other course material will be published via the web site, anything said or announced verbally during a lecture or lab is considered official, and will assumed as “common knowledge”. I frequently may verbally give exam or assignment tips in class, which may not appear in any document. Lecture attendance may be used in “borderline” situations in making a decision to “round up” to the next highest letter grade bracket. Other factors such as class participation, demonstrated effort, etc., may also be taken into account. The instructor’s or TA’s assessment of these factors is final. Role will be frequently taken in both lectures by passing around an attendance sheet. Because of the nature of the material in this course, it is my opinion that it would be very difficult to get a good grade with poor attendance.
SUBMITTING ASSIGNMENTS:
This is largely up to the TA – details will be posted later.
You are strongly urged to keep a backup of all assignments submitted – backups WILL be assumed in he event that an assignment gets lost.
EXAM SCHEDULE:
Term exam 1, part 1, Wednesday 3/5/03, Part 2 (optional), TBD (1 to 1.5 hours total)
Term exam 2: Wednesday 4/30/03 (1 hour total)
CS373 Spring 2003 Page 1 of 4
Final exam: as scheduled by registrar: Tuesday, 5/13/03, 2 - 4 PM, LH 9
Note: the final exam is comprehensive and will be two hours long.
ASSIGNMENT/EXAM REQUIREMENTS
1. Assignments are due on the date given in with the assignment and are subject to the "Late Policy" below and “Submission Policy” above.
2. All assignments or exams must be clearly and neatly written. Any material, which, in the opinion of the instructor/TA, is not clear or readable, will be subject to losing points. In grading exams or homework, I give myself a brief time to decipher handwriting and if in my opinion it is illegible, I will mark it wrong. I do not tolerate “smoke screens”, so give concise, easy to read answers ... by the way, I’m not good at reading tiny writing. It is strongly recommended that you type homework assignments.
Homework must be submitted in the following format:
- Printed or neatly handwritten on 8 ½ x 11 sheets of paper NOT having the ragged edge caused by ripping pages out of a notebook. Pages must be stapled NOT “dog-eared”.
- Pages must be numbered using the format: page n of m, where n is the current page and m is the total number of pages.
- Include a separate cover sheet containing your name, course and section, assignment number, and date of submission.
The grader reserves the right to deduct points for not following this format.
3. Reasonable discussion or brainstorming of assignments is acceptable, but the final work submitted must be done independently. COPIED MATERIAL (HOMEWORK OR EXAMS) WILL NOT BE ACCEPTED. ANY CHEATING SITUATION WILL BE TURNED OVER TO THE CS DEPARTMENT ADMINISTRATION WITH A RECOMMENDATION OF AN F IN THE COURSE, OR EVEN MORE SEVERE DISCIPLINARY ACTION. Based on my past experience, I strongly recommend that all assignments be submitted in sealed envelopes, especially when submitted in an unsecured place - for obvious reasons.
4. LATE POLICY: All assignments must be submitted by the day is is due. There are no grace periods - an assignment not turned in by the due date will default to a grade of zero. There are no makeups for missed exams or homework. The instructor or TA must be notified in advance if there is a conflict or other serious reason preventing you from taking an exam. The instructor/TA reserves the right to decide on the seriousness of such exceptions. Except for an emergency, if you simply do not show up for an exam, the grade is a zero with no makeup.
5. “Statute of Limitations”: In the event that an assignment or exam is missing, it is the responsibility of the student to report this to the instructor within one week after this assignment or exam was returned to the class (excluding official BU breaks). No consideration will be given to such situations after one week. For example if a zero was given because an assignment was not turned in, and the student never notified the instructor of the apparent loss within one week after the return date, the zero will not be negotiable. It is your responsibility to claim returned materials.
REFERENCES:
Lewis & Papadimitriou, "Elements of the Theory of Computation", 2nd Edition, Prentice-Hall, 1998
Thomas A. Sudkamp, “Languages and Machines”, 2nd Edition, Addison-Wesley, 1997
Hopcroft & Ullman, “Introduction to Automata Theory, Languages, and Computation”, Addison-Wesley, 1979
Dean Kelly, "Automata and Formal Languages", Prentice-Hall, 1995
Dexter Kozen, "Automata and Computability", Springer-Verlag, 1997
Fletcher R. Norris, “Discrete Structures: An Introduction to Mathematics for Computer Science”,
Prentice-Hall, 1985
John C. Martin, “Introduction to Languages and the Theory of Computation”, McGraw-Hill, 1991
J. Glenn Brookshear, “Theory of Computation Formal Languages, Automata, and Complexity”,
Benjamin/Cummings, 1989
Floyd and Beigel, “The Language of Machines”, W. H. Freeman and Company, 1994
FINAL NOTE:
I extensively use the “Electronic Study Group” System (a listserv) to keep in touch with the students. Frequently important items will be communicated by this means, for example, an assignment or change in an assignment, or useful “tips” on an assignment or project. Announcements given via listserv are considered official, so make sure you get on the listserv. The listserv is also intended for you to discuss projects etc. with the rest of the class. So check your email frequently, and remember that anything said on it is public. Also it must only be used for course related messages.
CS373 Spring 2003 Page 1 of 4