Syllabus for CIS 770, Formal Language Theory, Spring 2008

Professor: Rod Howell

Office:227D Nichols
Email:rhowell@ksu.edu
Office Hours: 10:30-11:30 MWF, or by appointment

TA: TBA

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

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. 20: 15%
Exam 2, Mar. 14: 15%
Exam 3, Apr. 21: 15%
Final Exam, Fri., May 16, 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 (in hard copy only) 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

Kansas State University has an Honor & Integrity System based on personal integrity, which is presumed to be sufficient assurance in academic matters that one's work is performed honestly and without unauthorized assistance. Undergraduate and graduate students, by registration, acknowledge the jurisdiction of the Honor & Integrity 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.

A component vital to the Honor & Integrity System is the 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."

In this class, you may discuss homework problems with others; however, you must write up your own solutions yourself, without using either complete or partial solutions from your classmates, the internet, or other sources. You must do the exams with no assistance from others. If you are in doubt about what is permissible, please ask me.

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.

For more information, visit the Honor & Integrity System home 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 2008, 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.