T-79.148 INTRODUCTION TO THEORETICAL COMPUTER SCIENCE
Notes on the examination requirements (HH Autumn 2003)
Basically the exam problems will be similar to the
home assignments of the course, i.e. the three first
problems in each week's problem set. With reference
to the lecture notes, the main rule is that all and
only the non-starred sections in the lecture notes are
included in the exam, with the following exceptions:
- Writing recursive-descent parsers for LL(1) grammars
(Sec 3.4) is NOT included. (Although this is a basic
skill for every computer scientist/engineer, it belongs
more properly in the domain of the compiler writing course.)
- Chomsky normal form and the CYK algorithm (Sec 3.6)
ARE INCLUDED even though starred in the notes.
- Concerning unrestricted and context-sensitive grammars
(Sec 5) ONLY the definitions and statements of the
theorems are included, NOT the proof constructions.
(The reason for this is that there were no home problems
on this topic this spring.)
- Concerning Rice's Theorem (Sec 6.7), the statement
and applications of the theorem must be known, but
NOT the proof construction. (However this is a curious
proof, so you might want to read it just for enjoyment.)
A brief outline of the topics included and not included
in the exam per subject area follows:
1. Basic mathematics
Correct usage of basic notions (sets, relations, strings,
languages etc.) is required throughout the exam, but
there will be no specific problems addressed to this part.
2. Finite automata and regular languages
Everything discussed in the lectures and home assignments
is fundamental exam material, including implementations
of finite automata in some programming language and
(especially!) the pumping lemma for regular languages.
3. Context-free languages and grammars
Everything discussed in the lectures and home assignments
is included, with the exception of recursive-descent
parsers (cf. above) and the context-free pumping ("uvwxy")
lemma. Concerning pushdown automata one needs to be able
to write simple PDA's and know that (nondeterministic) PDA's
recognise exactly the context-free languages; however the
proof construction for the latter result is not required.
(It is also not presented in the current version of the
lecture notes.)
4. Turing machines
Everything discussed is included.
5. Unrestricted and context-sensitive grammars and languages
Familiarity with the definitions and basic characterisations
(type 0 grammar ~ Turing machine, type 1 grammar ~ LBA)
is required, but the proof constructions for the results
are not required. (Cf. above.)
6. Computability theory
Basic results and constructions up to and including Rice's
theorem are included in the exam; however the proof of
Rice's theorem is not required (cf. above). The topics of
recursive functions, reductions, and RE-completeness are
also not required.
The exam problems can be classified into three types:
1. Problems testing basic familiarity with the notions
discussed, e.g.:
- "Define the notions of recursive and recursively enumerable
languages"
- "Is is true that all recursively enumerable languages can be
recognised by deterministic Turing machines?"
- "Is it true that any nondeterministic pushdown automaton
can be simulated by a deterministic one?"
2. Construction problems, e.g.
- "Give a deterministic finite automaton recognising the
language described by the regular expression..."
- "Minimise the number of states in the following deterministic
finite automaton..."
- "Give a context-free grammar generating the following
language..."
- "Show that the following context-free grammar is ambiguous..."
(This looks like a proof problem, but what is actually
requested is the construction of two different parse trees
for some sentence.)
- "Design a (deterministic) Turing machine for the following
task..."
3. Proof problems
- Here the all-time favourites are the applications of the
pumping lemma for regular languages: "Show that the following
language is not regular:..." In this case a full and careful
argument is required as an answer.
- Another type of proof problem requires combining some
basic notions in a construction or argument of a general
nature, e.g.
- "Prove that if L is a regular language, then so is
L^R = { w^R | w \in L }." (Solution requires a simple
manipulation of the finite automaton recognising L.)
- "Prove that the union of two context-free languages
is context-free". (Solution requires combining the
respective grammars in a simple way.)
- "Prove that all context-free languages are recursive."
(Solution requires observing that e.g. the CYK method
provides a total recognition algorithm for any context-
free language, and by the Church-Turing thesis this
can be implemented as a total Turing machine.)
- In the latter type of proof problems it suffices to present
a construction that is "obviously" correct, possibly augmented
with an example. I.e., the correctness of the construction need
not be further validated mathematically.