Office Tel.: 287-6472, Home Tel: 731-3297 (between
Office hours: Monday and Wednesday,
The theory of formal languages is a fundamental
theoretical discipline in Computer Science.
Its applications are mainly in the area of compiler design and
programming languages but many other areas (computational biology, operating
systems, computer networks, etc.) also benefit from its results.
The main reference for this course is Theory of Formal Languages with Applications by Dan Simovici and Richard Tenney,
published by World Scientific.
In general, every two lecture meetings will be followed by
a seminar dedicated to solving problems and helping you with the problems from the
homework.
We shall cover the following topics:
1.
Words, languages and free monoids.
2.
Finite state automata and regular languages.
3.
Rewriting Systems: semi-Thue
systems, grammars, the Chomsky hierarchy.
4.
Context-Free Languages.
5.
Pushdown automata.
6.
Applications to coding theory.
Things to remember:
·
This course is a quite mathematical one. This is why cs320 (Discrete Mathematics) is
an absolute prerequisite.
·
Grading will be based on homeworks
and two in-class tests (with open books).
·
No late homeworks will
be accepted. Your homework must be
entirely yours. Presentation of homeworks and examinations
is very important. What you know well you express well. You should write in a neat and legible way
and, preferably, learn LaTeX and use it for your homeworks.
·
Learn the Greek alphabet.
I wish you a happy and productive semester!
Homeworks will be posted below: