Computer Sciences 341 - Automata Theory
                                                 Fall 2011

Mary Eberlein, Ph.D.
Painter 5.44
eberlein at
Office Hours: W 2-3:30 in PAI 5.35, and by appointment (email me several suggested times)
Course web page:

Teaching Assistant
  Hongkun Yang (yang.hongk at
  Office Hours: F 2-3:30 in PAI 5.33
  Problem sessions: M 6:30-8 pm in BUR 116

  Fred Kuo (fredkuo at
  Office Hours: Th 11-2 in PAI 5.33

Textbook and other materials
Introduction to the Theory of Computation, 2nd edition, by Michael Sipser
Handouts given in class and posted on course webpage

Covered Material
Regular Languages
Context-Free Languages
Turing Machines


I think we all wish that we could have courses without grades. You hate worrying about grades. I hate having to assign grades. But grades are essential to insuring that your degree has the value that it deserves. So we have a grading system and that system has to have two essential properties:
-It has to be fair to everyone in the class.
-It has to be a true measure of how much each student knows about the class material.
The system I will use in this class will assign grades as follows:
  3 exams (Oct 3, Nov 7, final exam slot)                      (20%, 20%, 35%)
Homework assignments                                               15%
Quizzes and class participation                                    10%

The standard letter grade cutoffs will be applied, i.e., 90 - 100 % is an A, 80 - 89 % is a B, etc. It is possible that these cutoffs may be changed to the benefit of the students at the instructor's discretion.

The exam dates given above are tentative and may be changed. The midterm exams will be given in the evening.

Your grade records will be maintained by your TA on egradebook. If you have questions or concerns about your grade, contact the TA first.

Assignments and Exams
No late assignments will be accepted.  There will be no makeup exams unless you have another class at the time of the exam, and a missed test without a written, verifiable emergency, medical, religious, or participation in a varsity sporting event excuse provided to the instructor will count as a zero. Emergency excuses can be provided after the test. All other excuses must be provided one week before the test. With such an excuse your midterm exam grade will be replaced by your final exam grade. With such an excuse a makeup final exam will be given.

Assignments will usually be given every week. The due date for each assignment will be clearly stated. Respect Murphy's rule and plan for your bus to run late, your personal computer to crash the morning of the due date, etc.

Homework assignments must include: your name, the assignment number, and your EID. Staple your homework solution set so that no pages will be lost. Please turn in either legible handwritten solution sets or solutions produced with a word processor.

Collaboration on Assignments
You are encouraged to study for exams together, work example problems together and to discuss high level approaches to solving the homework problems. But the moment you start looking at another student's homework solution or solutions from any other source, or discussing solution details with someone other than the instructor or TA, you have crossed the line into cheating.

Exam Topics
Exams will cover material from lecture, assignments, and assigned readings. Exams will be cumulative, but they will be more heavily weighted towards material which has not yet been tested.

Announced and pop quizzes will be given frequently. Your lowest quiz grade will be dropped. No makeup quizzes will be given. I suggest that you plan to attend all classes and discussion sections so that you may drop a quiz you miss because of illness or emergency.

Grade Changes
If you are dissatisfied with any grade you receive, you must present a written complaint to your TA. The complaint must be submitted within one week of the date on which we first attempted to return the graded work to you. Your complaint must contain supporting evidence and arguments which explain why your work was graded incorrectly. It is not sufficient to submit a note that says "regrade question 3", for example. Grade change requests that do not meet these requirements will not be considered. Note that assigned grades are not the starting point of a negotiation. This isn't a weekend bazaar. Unless we have made a mistake in grading your work (i.e., you have a correct answer that was marked wrong, or your score was added incorrectly), your grade is final.

Note that none of the following grade discussions is appropriate:
(1) "I know my answer was wrong, but I deserve more partial credit points." When we grade, we make decisions about how many points to give for various kinds of wrong answers. This is never a clear cut decision. The important thing is that we make some decision and then implement it fairly for everyone. It is completely unfair to come back later and give one person more points just because they ask. We won't do it.
(2) "I don't like my final grade. It will ruin my life for the following reason: ... Therefore you should give me a better one." Class grades reflect only one thing: how well you did in the class. Life circumstances just don't play a role here. Don't come to me with this kind of argument.
(3) "I don't like my final grade. I am desperate. Isn't there some sort of extra credit thing I could do?" Any answer other than "No" to this question would be completely unfair to other students in the class unless they were all offered this option. That would be equivalent to saying that the semester isn't over and everyone can keep trying. We're not going to do this. Final grades are final.
(4) "I don't like my final grade. Can I have an incomplete and try again?" There are University rules for giving incompletes. If you meet those rules (e.g., you had a medical problem during the semester), then, of course, come and tell me and ask for an incomplete. But make sure you do it as soon as you can. Do not wait until the semester is over. If you do not meet the rules, the answer is "No".
(5) "I don't like my final grade. It doesn't reflect what I really know. I guess I didn't show what I know on the exams, but won't you give me a chance to convince you that I really know this stuff." Again, any answer other than "No" would be unfair to everyone else.

Some of the comments above are based on the computer science department's code of conduct.

Study Groups
Please organize yourselves into study groups of 3-5 students who will meet once a week to discuss the course material. Please submit to your TA by the fourth class meeting the members of your study group and the place and time of your meetings.

Academic Honesty and Inappropriate Collaboration
We follow the University's standard policies on academic honesty. They will be rigorously enforced. Cheating will result in action commensurate with the policies stated in the University's Manual on Academic Honesty. At the very least cheating will lead to an automatic F in the class and a referral of the case to the Dean of Students Office. Additional penalties, including suspension or expulsion from the University, may be imposed by that office. You are expected to do all work individually unless explicit permission for group work is given.

Every piece of work that you submit with your name on it must be yours and yours alone. Students may not acquire from any source (e.g., another student or an internet site) a partial or complete solution to a problem that has been assigned.

Students with Disabilities
The University of Texas at Austin provides upon request appropriate academic accomodations for qualified students with disabilities. For more information, contact the Office of the Dean of Students at 471-6259, 471-4641 TTY.