T-79.148 INTRODUCTION TO THEORETICAL COMPUTER SCIENCE Notes on the examination requirements (PO 3 May 2002) 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.