Syllabus for CIS 770, Formal Language Theory, Spring 2007

Professor: Rod Howell

Office:227D Nichols
Email:rhowell@ksu.edu
Office Hours: 1:00-2:00 MWF, or by appointment

TA: Aaron Chavez

Office: Nichols 019, Desc CC
Email: mchav at ksu.edu
Office Hours: 3:00-4:00 TT

Textbook:

Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Addison Wesley, 3rd Ed. Also see the textbook's home page.

Prerequisite:

CIS 570 Introduction to Formal Language Theory

Specifically, students are expected to have the following background:

Experience doing formal reasoning about automata, grammars, and formal languages
Understanding of basic concepts of set theory, functions and relations, and propositional and predicate logic (see Chapter 1 of the textbook)
Ability to write rigorous proofs, similar to the proofs in Chapter 1 of the textbook

Goals:

To develop understanding of the use and properties of the common classes of formal languages, grammars, and automata
To develop mathematical creativity
To develop mathematical rigor in solving theoretical problems
To develop skills in the written communication of rigorous problem solutions

Topics:

We will cover most of the material in Chapters 1-9. Much of the material in Chapters 1-5 is covered in prerequisite courses. In some cases, we will briefly review this material, but in other cases, we will examine the concepts in greater depth. If time permits, we may cover additional material from Chapters 10-11.

Grading:

Homework: 15%
Exam 1, Feb. 9: 15%
Exam 2, Mar. 9: 15%
Exam 3, Apr. 13: 15%
Final Exam, Tues., May 8, 11:50 am: 30%
Participation: 10%

Homework problems will be assigned throughout the semester. We will spend significant class time discussing some of the problems before they are due. It is therefore important that you attempt to solve problems before the date on which they will be discussed, so that you will be able to participate in the discussion.

Assignments may be submitted to either

Rod Howell; or
the homework tray in the CIS office, Nichols 234 (be sure to include your name, my name, and the course number).

Assignments submitted to any other person/location or after the due date will not be accepted.

Grades will be assigned according to the following scale:

80-100: A
60-79: B
40-59: C
20-39: D
0-19: F

Academic Honesty

It is expected that all homework and exams that you submit for grading are your own work, i.e., the results of your own creative thoughts expressed in your own words. The homework assignments are given to help you to learn how to solve problems in automata and formal language theory. Often the learning process is aided by discussions of homework problems with others. Such discussions are not prohibited. However, though you may receive some key insights from such discussions, you are expected to work out the details of solutions on your own and to write them up yourself.

Any attempt to represent as your work any work done by any other person (KSU student or otherwise) will be considered to be cheating. Anyone caught cheating will receive a 0 for that assignment or exam. More serious offenses may result in an F for the course or dismissal from the University. All cheating incidents will be reported to the K-State Honor and Integrity System and to the Department Head.

According to the K-State Honor and Integrity System System, on all assignments, examinations, or other course work undertaken by students, the following 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." For more information, please visit the Honor System web page at http://www.ksu.edu/honor.

K-State Online

All assignments and other course materials will be distributed via K-State Online. Grade information may be accessed there, and a Message of the Day may be available at times. Important class messages will be emailed to your KSU email accounts and posted as the Message of the Day. You must be enrolled in the course to access K-State Online.

Other

College of Engineering Policies

Copyright 2007, Rod Howell. This syllabus and all lectures for this course are copyrighted materials. 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 Rod Howell.