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*