CS532: Formal Languages
[ Info | Theme
| Textbook | Lectures | Homework | Exams | Grading
| More ]
Course Information
Lecturer: Xiang-Yang
Li, xli@cs.iit.edu
Office Hours: 4:00PM-5:00PM (M,W), or by appointment.
Office: 237D, SB
Phone: 567-5207
TA: TBA
Office Hours: 3:00PM-4:00PM (M,W) or by appointment.
Office: TBA
Start Date: 8-27-01; End date12-7-00.
ClassTime: 5:00PM-6:15PM (M,W)
Classroom: 220 SB.
The class homepage is http://www.cs.iit.edu/~xli/cs532.html.
All handouts and important information will be posted there. Please check it
for new information.
Course Theme
This course provides an introduction to the theory of formal
languages and machines. We start by defining strings, alphabets, and languages.
We then define grammars of different kinds and introduce the Chomsky Hierarchy
of languages and corresponding machines. The first half of the course, up
through the midterm is centered on regular sets and finite automata. The second
half will be spent mostly on context free languages of various types, but we
will define Turing machines and introduce the question of decidability at the
end. Particular topics to be covered include:
- Finite automata, regular
languages, and regular grammars.
- Deterministic and
nondeterministic computations on various automata.
- Context free grammars,
languages, and pushdown-automata
- Turing machines, Church's
thesis, and undecidable problems
- Computational complexity,
polynomial-time reductions, NP-completeness, and Cook's theorem.
Textbook
The
official course text is Introduction to Formal Languages & Automata
2nd 97 ; Peter Linz; Hardcover, 377 pages; Jones and Bartletts, 1997, or
Introduction to Formal Languages & Automata 3rd 2000 ;
Peter Linz; Hardcover, 410 pages; Jones and Bartletts, 2000. ISBN 0-7637-1422-4
One useful text is Elements of the Theory of Computation -
2nd. ed.; Harry R. Lewis, Christos H. Papadimitriou; Hardcover, 352
pages; Prentice-Hall, August 1997.
Another
useful text, that is also a classic, is Introduction to Automata Theory,
Languages, and Computation; John E. Hopcroft, Jeffrey D. Ullman;
Hardcover, 418 pages; Addison-Wesley, April 1979.
You
will also find another text useful later in the course: Computers and
Intractability: A Guide to the Theory of NP-Completeness; Michael R.
Garey, David S. Johnson; Paperback, 338 pages; W. H. Freeman & Co., June
1979.
Lecture Notes
The course will be more likely organized as following.
- Week 1. Introduction.
- Week 2. Finite Automata.
- Week 3. Regular Expressions.
- Week 4. Finite Automata with
Output.
- Week 5. Pumping Lemma for
Regular Sets.
- Week 6. Myhill-Nerode
Theorem.
- Week 7. Midterm (date to be
announced)
- Week 8. Context-Free
Grammars.
- Week 9. Simplification of
CFG's.
- Week 10. Chomsky and
Greibach Normal Forms.
- Week 11. Push-Down Automata.
- Week 12. Pumping Lemma for
CFL's.
- Week 13. Closure Properties
and Decision Algorithms.
- Week 14. Turing Machines and
Undecidability.
- Week 15. Final Examination.
I will try to put online lecture notes if possible. For more, see lectures.
Homework
- There will be problem sets
roughly every week, usually released on the last lecture of that week, and
due by the beginning of the first class of the next week.
- You may take an automatic extension
by handing in the assignment on the specified extended due date and time
(usually the following Wednesday by the end of class) but with 10% deduction on this homework grade.
- No late assignments handed in after the extended deadline will
be accepted. Requests for
an additional extension will almost always be denied.
- In this course you are allowed to discuss the problems with
your classmates, and to work together. If you choose to do so, please
indicate the name(s) of the people with whom you have worked. Otherwise,
it will be treated as cheating! Keep in mind that you may discuss assignment
problems, general proof strategies, or general algorithms with other
students in the course, but you may not collaborate in the detail
development or actual writing of problem sets. Consulting with
students outside of the course, or using past notes or solutions, etc., is
expressly forbidden. Refer to the Campus Code regarding academic
integrity.
- Please help us by stapling all written pages, labeling them
with your name, and clearly labeling each problem. You don't want us to
lose part of your assignment or not see your answers, do you?
See some Guidelines for Written Homework (by Prof.
L. Pitt from UIUC).
Examinations
There will be one midterm exam, and one final exam.
The midterm exams will probably be scheduled for the evening. Details will be announced
via the class homepage soon. You will be responsible for all material covered
in lectures, homework, and assigned readings.
Grading Policy
Tentative weighting
scheme is as follows. However, the instructor reserves the right to make
adjustments to these weights based on his a posteriori evaluation of the
relative difficulty and fairness of the exams and homework.
- Homework 40%,
- Midterm Exam 30%
- Final Exam 30%.
Each
problem will be graded 80% for correctness and 20% for style and clarity. Good
style means giving a sound logical argument and a clear presentation,
sufficient to convince someone who knows the material, but not the answer, that
your answer is correct. Consider your audience to be a skeptical classmate.
Good style also implies that an answer should be reasonably thorough, as well
as reasonably concise.
Note: In order to
pass the class, you must do sufficiently well on each of the categories
in the table above. In particular, credit will not be given to those who skip
much homework and rely on stellar exam scores.
Regrades: If you feel
that a problem was graded incorrectly, please contact the teaching assistant
first. Contact the instructor if there is still a disagreement. For best
results, please attach a short note stating what you want regraded and why.
We
want everyone happy and satisfied in learning.
How
To Get The Most Out Of This Course?
Last modified: Thu Jul 20 16:54:22 CDT 2000