COP 5310: THEORY OF AUTOMATA AND FORMAL LANGUAGES -Spring 2001- Mike Burmester


COP 5310: THEORY OF AUTOMATA AND FORMAL LANGUAGES


General Information

Objectives

The objectives for this course are to learn how to apply formal models of computation to specific examples and to study the general properties of these models. The models include:

Emphasis will be given to:

The concepts of this course are mathematical in nature and reasonably sophisticated. You will be in the best shape if you have some degree of familiarity with proofs and manipulating mathematical symbols.
You should expect this course to be rather challenging, but stick with it. The best way to learn the material in this course is to spend some time on it. You must read the book and do the problems.

Prerequisites

COT 4020 and COT 4210.

Text

Other Texts

There are several other textbook that may be of help in getting background information or in getting a different perspective that you may find interesting. You will find it helpful to visit the library. For example, you could check:

Plan

The course will start with an overview of Chapters 2 through to Chapter 6, at roughly one chapter per week. In class we will discuss the proofs of selected theorems and some examples. On your own you will be expected to read the chapters and do the exercises.
We will then gradually slow down as we move into Chapter 7 (Turing Machines), Chapter 8 (Undecidability), and Chapter 9 (Chomsky Hierarchy).
Finally we will cover Sections 1 through to Section 5 of Chapter 13.
A more detailed course plan will be handed out in class.

Homework and plagiarism policies

You will be given homework assignments. These will help you learn the material by working at it. Try to be tidy and write legibly and remember to print your name on every page that you hand in.
Homework is due at the beginning of the class on the day specified on the assignment. Late homework will only be accepted at the beginning of the next class period and will marked down by 10%. After that, late homework will not be accepted.
Treat graded homework assignments as take-home tests. Do the work yourself: no one else should look at your paper. Giving or accepting help on graded homework assignments is a violation of the student honor code.
Of course it is unrealistic to assume that you will not talk to other students about hemwork problems, but it will be considered a violation of the student honor code to turn in uncredited work that is not your own. If you do talk to other students about the problems make certain that your write-up is your own. If you find a solution to a problem in a book or somewher else, the reference should be cited.
Since the course and the tests will be based on problem-solving skills learned by doing the homework, the more time and effort you are able to put into your homework the better the shape you will be in for your exams.

Study Habits

You have to study the text outside class in order to strengthen your understanding of the material. You might also want to read material before class, and then again in greater detail after class. This is very good practice.
Many students complain that even though they understand a subject they do not do well in the exams. The problem is that understanding is different from learning. Learning involves active engagement, whereas understanding is passive. In subjects such as this one it is very important to assimilate new concepts.
If you get stuck on a detail and cannot work it out, get help. I will be glad to help.

Grading

The homework assignments will determine 50% of the final grade. Each assignment will have a point value and a due date. Any assignments received between the due date and the next class meeting will have the score reduced by 10 percent. After that assignments will not be accepted. Homework assignments must be tidy and legible.
There will be two midterms and one final examination contributing 10%, 10%, 25% to the final grade, respectively.

Attendance

You are required to attend all class meetings. Attendance and class participation will have a strong effect on your grade both directly and indirectly. Class attendance and participation will contribute 5% towards your final grade.
If you are forced to miss a class, it is your responsibility to get good class notes from a friend. Check with me for handouts.

Academic Honor Code

You are required to read the FSU Academic Honor Code and abide by it. First violations will result in lowering of the final course grade by one whole letter. Repeat violations will result in a grade of F with no provision for retaking the course.
Work handed in must be the result of your own independent effort. All work that you claim to be yours, must be yours.
What does ``individual work'' mean? An intelligent person searches publications (including the web) for information, and ideas. If you use such information you must give credit to the source.

Accommodation for Disabilities

Students with disabilities needing academic accommodations should:

  1. Register with and provide documentation to the Student Disability Resource Center (SDRC).
  2. Bring a letter to the instructor from the SDRC `indicating you need academic accomodations. This should be done within the first week of class.

This syllabus and other class materials are available in alternative format upon request.

For more information about services available to FSU students with disabilities, contact the Assistant Dean of Students:

Student Disability Resource Center
08 Kellum Hall
Florida State University
Tallahassee, FL 32306-4066

e-mail: sdrc@admin.fsu.edu
phone: (850) 644-9566.

Communication

You are required to check regularly for electonic mail sent to you containing information about this course. You are also encouraged to use e-mail to ask questions and report problems. As a student in the course you will have a user ID in the Department of Computer Science. If you want e-mail sent do another address, make sure you give the course supervisor your preferred e-mail address. If you are experiencing difficulty or are concerned about your progress, please contact the instructor.

Assignments and Tests

.

M. Burmester
Last modified: April 23, 2001