CIS 770. Formal Language Theory, Spring 2010


Basics

Instructor: Torben Amtoft

Required Textbook

Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft & Rajeev Motwani & Jeffrey D. Ullman, Addison Wesley, 3rd edition.

Prerequisites

In principle, students should have taken CIS570 (Introduction to Formal Language Theory), or an equivalent course. Specifically, students are expected to have the following background:

Expected Outcome

Topics

The early part of the course will be based on Chapters 1-4 of the textbook; much of this material may be review, but it is necessary to cover it in order that the proper foundations are laid. The core of the course is taken from Chapters 5-9, with material from Chapters 10-11 being covered if time permits.

Grading

Class participation involves not just being physically present, but also actively contributing to the learning climate, by answering questions, doing simple exercises on the board, asking interesting questions, etc.

You should expect that it requires 80 % to earn an A, 60 % to earn a B, 40 % to earn a C, and 20 % to earn a D. In general, my approach to grading is expressed well by this piece by S.A. Miller.

Homeworks

are due frequently. There are two kinds of homework exercises: Assignments that are late will not be graded, unless in case of documented medical or family emergencies.

Exams

will be open book but you cannot bring any other material. The final is comprehensive, but with emphasis on the last part of the course.

Grievances

If you think that the instructor has made an oversight when grading your test or your homework, you are of course very welcome to ask for clarification. But complaints about judgment calls, like how much credit to give for a partially correct solution, are not encouraged---it is like arguing balls and strikes. In particular this holds for homeworks (since each assignment carries so little weight towards the final grade).

Academic Honesty

Kansas State University has an Honor System based on personal integrity, which is presumed to be sufficient assurance that, in academic matters, one's work is performed honestly and without unauthorized assistance. Undergraduate and graduate students, by registration, acknowledge the jurisdiction of the Honor System. The policies and procedures of the Honor System apply to all full and part-time students enrolled in undergraduate and graduate courses on-campus, off-campus, and via distance learning. The honor system website can be reached via the following URL: www.ksu.edu/honor . A component vital to the Honor System is the inclusion of the Honor Pledge which applies to all assignments, examinations, or other course work undertaken by students. The Honor Pledge is implied, whether or not it is stated: "On my honor, as a student, I have neither given nor received unauthorized aid on this academic work". A grade of XF can result from a breach of academic honesty. The F indicates failure in the course; the X indicates the reason is an Honor Pledge violation.

You are very welcome to discuss the course material, as well as specific questions, with your fellow students. However, all submitted answers must be your own work: you are not allowed to show your answers to anyone else, or look at the answers of any other student; neither are you allowed to consult previous model solutions that may be around, or solicit the Internet for solutions to specific homework problems. If you are in doubt about what is permissible, please ask me.

Academic Accommodations for Students with Disabilities

Any student with a disability who needs an accommodation or other assistance in this course should make an appointment to speak with me as soon as possible.

Expectations for Classroom Conduct

All student activities in the University, including this course, are governed by the Student Judicial Conduct Code as outlined in the Student Governing Association By Laws, Article VI, Section 3, number 2. Students who engage in behavior that disrupts the learning environment may be asked to leave the class.

Acknowledgment

Much of this syllabus is adapted from the course taught by Rodney Howell.


Copyright 2010 (Torben Amtoft) as to all lectures. During this course students are prohibited from selling notes to or being paid for taking notes by any person or commercial firm without the express written permission of the professor teaching this course.


Torben Amtoft