CIS 770. Formal Language Theory, Spring 2014
- Classes are MWF, 9:30-10:20am, in Nichols 236.
- The Captain's log
gives up-to-date information about
what has been covered so far and what is expected to happen
in the near future.
K-State Online is used
to report grades, and to upload material relevant for the course
(slides, assignments, model solutions, etc.)
Email: tamtoft hat ksu dot edu
Office: 219C Nichols
Office Hours: Tuesdays 2pm-4pm, and by appointment
Introduction to Automata Theory, Languages, and Computation,
John E. Hopcroft & Rajeev Motwani & Jeffrey D. Ullman, Addison Wesley,
Students should preferably have taken MATH 510
(Discrete Mathematics), or an equivalent course.
Specifically, students are expected to have the following background:
Understanding of basic concepts
of set theory, functions and relations,
and propositional and predicate logic.
Ability to write rigorous proofs,
similar to the proofs in Chapter 1 of the textbook.
To develop understanding of the use and properties of the
common classes of formal languages, grammars, and automata.
To develop mathematical rigor in solving theoretical problems.
To develop mathematical creativity.
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.
If time permits, we may also look briefly into temporal logics.
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.
Homework: 20 %
Exam 1, March 5: 20 %
Exam 2, April 16: 20 %
Final Exam, May 14: 30 %
Class participation: 10 %
Grades are curved, but as a rule of thumb, 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
piece by S.A. Miller.
There are two kinds of homework exercises,
with the former contributing the majority of the total
Assignments that are late
will not be graded,
unless in case of documented medical or family emergencies.
There will be frequent (15-20 during the semester) assignments
Instructions for using it will be posted on K-State Online.
There will be around 7 "manual" assignments, to
be handed in on paper:
either to me in class,
or to the homework tray in the CIS office, Nichols 234 (please make
sure to include your name, my name, the course number,
and that they stamp it with not only the date but also
the time of day).
will be closed book but you can bring up to 4 sheets (double-paged)
of hand-written notes.
The final is comprehensive,
but with emphasis on the last part of the course.
In case you miss an exam due to a documented medical or family
emergency, and a make-up exam is not possible, you'll be assigned
for that exam the average score of your other two exams.
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).
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:
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.
Students with Disabilities
Students with disabilities who need classroom accommodations, access
to technology, or information about emergency building/campus
evacuation processes should contact the Student Access Center and/or
their instructor. Services are available to students with a wide
range of disabilities including, but not limited to, physical
disabilities, medical conditions, learning disabilities, attention
deficit disorder, depression, and anxiety. If you are a student
enrolled in campus/online courses through the Manhattan or Olathe
campuses, contact the
Student Access Center
at email@example.com, 785-532-6441; for Salina campus, contact
the Academic and Career Advising Center at firstname.lastname@example.org,
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 V, Section 3, number
2. Students who engage in behavior that disrupts the learning
environment may be asked to leave the class.
Much of this syllabus
is adapted from the
Copyright 2014 (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.