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.