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

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

100 marks total

* 1: 20

* 2: 40
  - 2a: 20
  - 2b: 20

* 3: 40
  - 3a: 7
  - 3b: 3
  - 3c: 30

Notes
-----

* 1. Two common mistakes. The first is to tacitly treat E, F, G
     as sets, + as union on sets, and juxtapositioning as
     concatenation on sets.

     However, E, F, G are *not* sets. They are *variables* (or names)
     standing for some unspecified regular expression.

     L(E), L(F), L(G), on the other hand, are the sets denoted by
     the regular expressions E, F, G respectively (whatever these
     expressions are).

     The other mistake was to treat E, F, G as symbols, and then saying
     e.g. L(E) = {E}.

     This is plain wrong. L(E) is the set of words denoted by the
     regular expression E. For the sake for argument, we could have
     E = a+b+c, in which case L(E) = L(a+b+c) = {a, b, c}.

     However, {E} is a *singleton* set of the word E, i.e. a string
     representing a regular expression. So, in the case E = a+b+c,
     {E} = {a+b+c}.

     Clearly, {a, b ,c} /= {a+b+c}. The former is a set of *three*
     words, a, b, c; the latter a singleton set of the word "a+b+c".

     What the function L does is,in effect, to *interpret* the word "a+b+c"
     as a regular expression to give the meaning of that expression as
     a set of words.

     I recommend that you ponder over the above! It is important to
     understand the difference between the *representation* of a
     a language, such as a regular expression, or a DFA, and the
     language they *represent*.

* 2. Some people attempted to first simplify the given RE symbolically.
     But that was NOT what the question was asking you to do.
     Just apply the craphical construction to the given expression,
     exactly as it is, unwinding its structure until you hit
     the base cases, and then go back up, step by step,
     combining the resulting NFAs.

     Moreover, many who attempted to simplify made severe mistakes.
     In particular, note that, in general, for regular expressions E and F,

         (EF)* /= E*F*

     In this case, it means
 
         ((a + \epsilon)(b + c))* /= (a + \epsilon)*(b + c)*

     (There was another similar mistake in an earlier exercise. Recall that

         (ab)* /= a*b*