G52MAL UNMC 2010/11: Notes on Coursework, Exercises Set 1
=========================================================

First of all, the key to getting good marks for the weekly exercises, in-class
tests, and ultimately the exam, is not just to give correct answers, but to
*demonstrate* understanding.

This means that unexplained answers, or answers where the explanations
demonstrate clear gaps in the understanding, are likely to get low if any
marks.

The exception are questions that are phrased in such a way to make it clear
that just an answer is required.

Some further comments on this will be made related to specific questions
below.

Marking Scheme
--------------

100 marks total

* 1: 25
  - 1a: 5
  - 1b: 5
  - 1c: 10
  - 1d: 5

* 2: 25
  - 2a: 5
  - 2b: 5
  - 2c: 10
  - 2d: 5

* 3: 50
  - 3a: 20
  - 3b: 10
  - 3c: 10
  - 3d: 10

Notes
-----

* 1b. A number of people had correctly characterised the language of 1a as
  "all words over the given alphabet of lengths between 1 and 2". Yet, they
  included epsilon, the *empty* word, in the enumeration. The empty word has
  length 0! That is what it *means* to be empty. This would thus seem to
  indicate a profound misunderstanding. This time round, being the first
  coursework and all, I decided to mark fairly leniently. Had this been an
  exam, the marking could have been much harsher (depending on other
  circumstances) as it demonstrates misunderstanding rather than
  understanding.

* 1c. Here, the briefest possible answer for full marks is an expression that
  makes it clear that the answer is a SUM of the number of words of length m,
  m + 1, ..., n.

  Just stating the closed form expression is *not* a good answer without at
  least some explanation as to where it comes from and how it is related to
  the question, as this is not at all obvious from the expression itself,
  unlike the case where an explicit sum is given.

  Also make sure you understand the difference between a set, such as Sigma
  (set of symbols) or Sigma^2 (set of all words over Sigma of length 2), and a
  number, e.g. |Sigma|, the number of elements in the set (alphabet) Sigma, or
  |w|, the length of a word w. It is a formal error ("type error") to use
  arithmetic operations like + on sets and to use set operations like union
  and intersection on numbers.

* 2c. Keep in mind that epsilon is the unit of concatenation and simplify the
  final answer as far as possible. E.g., taking "e" to stand for epsilon,
  simplify a word like "ae" to "a", and "eee" to just "e".

* 3b. A number of people said that epsilon didn't belong to either L(A) or
  L(B) because epsilon is not a symbol of the alphabet. A profound
  misunderstanding! Epsilon stands for the empty *word*, i.e. it is *not* a
  symbol, and an epsilon will never (in the context of automata) be a symbol
  of an alphabet without somehow making the distinction between "epsilon the
  symbol" and "epsilon meaning the empty word" clear (e.g. by some
  typographical convention).

  In fact, epsilon/the empty word does belong to L(B) because the start state
  of DFA B is an accepting or final state which means it can accept the empty
  word (as the start state is where the DFA ends up if no input is read). The
  empty word does not belong to L(A) because the start state of A is *not* an
  accepting or final state.

  3c. In an explicit calculation, make the relation between the steps clear. 
  For example, if one expression is *equal* to another, *do* write "=" between
  them. For other steps, the relation could be an inequality (like "<=", "<"),
  or logical implication or equivalence (implication arrow and double
  implication arrow).

  A number of people had consistently omitted the equal signs in their
  derivations. This time, I marked leniently ...

  In some cases, the given calculations were very partial: effectively one
  step had been given, and then a big jump had been made to the final answer. 
  If you are asked to do a calculation, make sure each step is so small that
  it is completely obvious, otherwise provide an explanation/justification of
  the step.

* 3d. Note that the answer sought by a question phrased like this is a
  description in your own words, i.e. in plain English, that neatly
  characterises the language in question in a fairly intuitive, or at least
  easy-to-grasp, way.

  If you end up writing a very complicated explanation, e.g. effectively
  describing how the automaton operates, think again; i.e. try to see beyond
  the automaton to the language defined by it.

  Similarly, the question does not ask for the definition of the language
  accepted by a DFA to be transliterated into English.