This course is an introduction into the theory of computing.
We will learn the fundamental language classes (regular, context-free grammar, general grammar)
and their corresponding machine models (finite automata, pushdown automata, Turing machine).
We will also discuss problems that are undecidable in these models.
Finally, we will study complexity issues like NP-completeness.
The course is divided into four major topics.
First we introduce a simple computing model, the finite automata,
and characterize the languages that can be decided by these machines, the
Then we study the more powerful pushdown automata and their corresponding
languages, the context-free languages.
Finally, we will discuss Turing machines, the most powerful machine model.
But we will also see the limitations of this model; not all problems
can be solved by a Turing machine.
At the end, we will discuss efficiency of Turing machines, mainly in the forrm of
lower bounds, i.e., the theory of NP-completeness.
1. Finite automata and regular languages
We will introduce a simple machine model, the finite automaton (FA),
and study its computational power.
We will show that deterministic and non-deterministic FA can decide
exactly the same class of languages, the regular languages.
Regular languages are closed under all set operations.
We will learn algorithms to transform a non-determinisitcd FA into a deterministic FA,
to minimize the size of a deterministic FA, and to construct the regular language corresponding
to a FA (and vice versa).
We will also learn powerful methods to prove non-regularity of a language,
for example, the Pumping Lemma.
2. Pushdown automata and context-free languages
A pushdown automaton (PDA) is a FA with an additional stack to store information.
Non-deterministic PDAs can decide context-free languages (CFL), i.e.,
languages that can be described by a context-free grammar (CFG).
CFL are only closed under some set operations.
While most problems for FA are computable, some problems for CFG are undecidable.
We will see that we can parse context-free languages efficiently.
We will also learn powerful methods to prove non-context-freeness of a language,
for example, the Pumping Lemma.
3. Turing machines
A Turing machine (TM) is a FA with a memory tape.
It is the most powerful machine model known, but still there are problems that cannot
be decided by a TM, for example the Halting Problem.
We will learn Rice's Theorem, a powerful tool to prove undecidability.
There are many equivalent definitions of languages decidable by TMs,
for example general grammars, Post correspondence systems, lambda calculus, etc.
4. Complexity theory
In complexity theory we are interested in classifying languages
according to the efficiency of deciding them.
P (polynomial time) and NP (non-deterministic polynomial time)
are the most prominent classes, and we will study complete problems
(the most difficult problems in a class) for NP and PSPACE.
We will also shortly mention the concept of Kolmogorov complexity
which classifies languages according to the size of their most succinct representation.
This course will closely follow the textbook
Introduction to the Theory of Computation
by Michael Sipser, 2nd edition (English), China Machine Press, 2002.
It is mandatory that you have a copy of that book.
In class, I may sometimes teach material that is not in the textbook.
I may also skip some material in the textbook.
For the exams, however, I expect that you are familiar with everything we did in class,
everything covered by the textbook (except some parts
that will be explicitly excluded), and everything that appeared
in the homework assignments.
Usually, I will not provide any notes in addition to what you find in the textbook.
Below, I will provide links to some nice resources when we encounter them.
This course will be different from most courses you have experienced
so far at Fudan.
It will be a reading course, which means that
you must read the material covered in a lecture before you come to class.
You should work in teams (see below).
Your team must also send me an email every week (before Thursday 8pm)
with some problem you encountered in your class preparation.
Classes will always start with a short quiz
to test whether you are well prepared.
Then, instead of covering all the material step by step,
we will skip the more boring easy parts (like simple definitions)
and instead spend more time discussing difficult concepts or proofs.
If you come to class unprepared, you may have
difficulties with the quiz and may not be able to
follow the lecture.
This teaching method is called
Just-in-Time Teaching (JiTT)
and is advocated, for example, by
Eric Mazur at Harvard University.
JiTT is part of the
Interactive Learning Toolkit.
You can also
watch Prof Mazur
explain these concepts in his own class (skip the first ten minutes of the video...).
Here is the reading schedule for your class preparation.
Minor adjustments during the course are possible.
It might be helpful to check the webpage with
of the textbook.
The pages and section numbers refer to our textbook (2nd edition),
for a few topics there are also some notes of my own.
should guide you in your learning.
The FAQs are a list of your class preparation questions
together with my answers.
The Quiz column contains the class quizzes.
The last column contains the homework assignments.
|1: Mar 4
Basic definitions, DFA
|2: Mar 11
NFA, NFA=DFA, closure properties
|3: Mar 18
Regular expressions, Pumping Lemma
|4: Mar 25
and 2.1: CFG
|5: Apr 1
CFG=PDA, PDA, Pumping Lemma
|6: Apr 8
TM, Church-Turing, decidable languages
|7: Apr 15
||9 am, Room Z2102
|8: Apr 22
Halting problem, undecidable languages
|9: Apr 29
Post Correspondence Problem, reductions
|10: May 6
|11: May 13
|12: May 20
|13: May 27
Kolmogorov complexity, P
|14: Jun 3
|15: Jun 10
|16: Jun 17
On the day before each class before 8pm (i.e., every Thursday before 8pm),
each team must send me an email, worth 1 point, about
one topic in the material you were supposed to prepare
for the class that you found difficult
to understand (that could be a concept, a definition,
a proof, an example, etc.), or "No problems" if you had no problems.
This information will help me to focus on your difficulties
in my lecture the next day.
Every class will start with a quiz.
Usually, there will be six questions (multiple choice).
Usually, four questions will cover the material you had to read
in the textbook for that day (see the reading schedule),
and two questions will review some older material.
You must answer at least three questions correctly to get one point,
and you must answer at least five questions correctly to get two points.
To foster the team spirit (i.e., strong members helping
their weaker teammates preparing the material), one more point is awarded
to each team with an average (among all its members present in the
classroom) of at least four correct answers.
Only the team members present will get the team point.
It may happen during the term that you have a good reason
not to be prepared for the quiz.
Therefore, you are allowed to skip one quiz without a penalty,
but you must inform me by email before class that you want to
skip the quiz on a particular day.
There will be a weekly homework assignment.
Assignments will be available on this page as they become ready.
Corrections to the assignments, should any be necessary,
will be posted on the course homepage.
Some assignments will contain a challenge problem for bonus points.
All Assignments have equal weight (even if they have different number of points).
Solving homework problems should help you better understand the course material.
Therefore, you will get one point for each problem or subproblem
for which you provide some solution attempt, even it is not correct.
You get another point if your solution is (approximately) correct.
For challenge problems, you can get only one bonus point for correct solution.
There will be two exams in this course,
a midterm and a final exam.
You need at least 50% of the points to pass an exam.
For each exam you may bring a cheat sheet,
i.e., one piece of paper A4 on which you can write whatever you want
(it must be handwritten).
All assignments together (reading, homework, quiz) are worth
30% of the final mark.
You need at least 50% of the assignment points to pass the course.
Each exam counts 35%.
I reserve the right, where
appropriate, to adjust raw marks downward in the case of cheating and
upward in other situations.
The following table shows hows to calculate your final grade
from your raw marks.
In this course you will be working in teams.
Prefered team size is three or four students.
During the course, students will earn points individually
and teams will earn points.
Points earned by the team will be credited to each
Each team should have a speaker who is responsible for
sending me emails (necessary for some assignments) and
in turn distributing my emails to the team members.
Your first task will be to form a team.
Your first assignment will be for the team speakers to send me
the list of the team members (name and student ID).
This must happen
before Thursday, Mar 10, 8pm.
If you can't find a team, please send me email.
Students who have not joined a team before the deadline
will be randomly combined to form a team.
Collaboration between teams is not allowed and is treated
Problem solutions should be your own or your team's common work.
If you find a solution somewhere else (old lecture notes, text book,
WWW, etc.), clearly acknowledge the source.
The standard penalty for cheating on an assignment is as follows:
a grade of -100% will be assigned for the piece of work, with a minimum
deduction of 5% from the final grade.
This penalty applies to the cheater as well as the team that allows its solution
Assignments should be handed in class on the due date (Friday).
Late assignments are not accepted;
zero points are assigned unless there are extenuating circumstances such as
In such cases, please inform the instructor as soon as possible.
Note that university regulations require that if a student
completes an exam, the grade in the course (in particular, a
failing grade) will not be changed, even if the student subsequently
claims that his/her performance was affected by illness or other
personal problems and submits documentation.
Students who fail a course sometimes ask the instructor if they
can write another exam or do some extra work in order to raise
We do not offer supplementary exams or other
ad-hoc methods of raising marks.