Assessment

The unit is 100% assessed by a 2-hour written exam in the Winter assessment period (i.e. the week following Week 12 of TB1).

This exam is considered open book in the following sense: Candidates may bring to the exam room 1 double-sided A4 page of notes in any format.

In addition, most of the important definitions from the unit are available for your reference at the back of the exam paper.

The exam is a series of problems to solve in the same style as the weekly problem sheets. There will be questions covering material from all parts of the unit. The difficulty of questions is related to your possible marks in the following way:

• 1* questions only account for approximately 40% of available marks.
• 1* and 2* questions account for approximately 70% of available marks.
• 1*, 2* and 3* questions account for approximately 100% of available marks.

Unfortunately, this is not quite true for the practice paper below, due to the way it was assembled. Partial marks are given for partially correct answers. This is important, because you are unlikely to answer all the 3* question(s) completely correctly in the given time, but it is possible to obtain some marks for an attempt.

The distribution of marks by topic is as follows:

• 34 marks are available for questions on syntax.
• 33 marks are available for questions on semantics.
• 33 marks are available for questions on computability.

However, you should make sure you are confident on all topics because the exam will contain 1, 2 and 3* questions within each of these topics.

Typical examples of the shape of 1* questions (mostly mechanical tasks that require careful use of definitions but very little insight, or recalling facts):

• Recall some simple facts about the definitions we have studied, and their consequences, such as the meaning of state, decidable, abstract syntax tree, injective, computable etc.
• Deriving a string in a grammar, giving examples of strings in the language expressed by a grammar.
• Constructing a parse table for a grammar.
• Identify the different syntactic categories of the While language, e.g. arithmetic vs. Boolean expressions.
• Evaluate arithmetic and Boolean expressions in a given state using the denotation function.
• Construct derivations trees for While programs from a given starting configuration.
• Writing a While program to achieve some simple specification, or to show computability of some function.

Typical examples of the shape of 2* questions (mostly constructing simple objects – programs, proofs, derivations, grammars etc – to meet given requirements):

• Construct a grammar to express a certain language.
• Give an LL(1) grammar equivalent to a given grammar.
• Evaluate extensions to the While language with new language constructs or semantics.
• Reason symbolically about (extensions to) the While language, including partial correctness properties.
• Show that a (more complex) function is computable, by writing a While program.
• Prove simple properties of functions/combinations of functions (injectivity, surjectivity etc).
• Show that a predicate is decidable/semi-decidable.

A few typical examples of the shape of 3* questions, but 3* questions are often atypical and of a shape that you may have never encountered before during the unit.

• Show that a language can be expressed by a grammar, where there is some insight needed to first simplify the description of the language.
• Construct proofs by structural induction over expressions and statements.
• Construct, and justify the correctness of, loop invariants.
• Show that a predicate is undecidable.

Before the day of the exam, you should be confident in your ability to answer typical 1* and 2* questions.