===========================================================================
CSC 324               Assignment 1 -- Marking Scheme            Winter 2009
===========================================================================


NOTE TO STUDENTS:

You will find below the marking scheme used for your homework, including
the meaning of marking codes and number of marks associated with each one.
(Note that the weight of the questions was changed slightly compared with
the assignment handout, to account for the true relative difficulty and
amount of work involved in each question.)

This file also contains my instructions to the marker (so you can get an
idea of how the homework was marked) and the marker's comments about each
question.  Please take the time to read this carefully before you ask
questions about the grading of your homework!


NOTE TO MARKER:

Be picky!  On any homework, it is the responsibility of students to show
that they understand how to solve each problem and to write up their
answers carefully.  Remember that marking is not only about evaluating a
student's performance, but also mostly about giving them feedback so that
they can learn from their mistakes.  This is especially important for
students who made numerous or more serious mistakes, as they are likely to
need more feedback in order to understand why their answers were incorrect.

For each question, I list solution elements with an associated code for
writing on student papers (the letter(s) between underscores _) and a
number of marks.  There are also general errors (with associated codes)
given below, with a maximum number of marks to take off for each type of
general error (as a percentage of the value of the question).  You will
likely encounter other common errors, or maybe decide to break down the
marking scheme further.  Simply make note of these changes/additions to
the marking scheme, and introduce new code letters (or short words) to
allow you to quickly give accurate feedback to the students (both in terms
of what they did wrong and how many marks it cost them).  Your marking
comments will be included in this marking scheme and posted on the course
website so that students may look up the meaning of marking codes and
understand how their work was marked.


GENERAL ERRORS (marked negatively, in addition to any other errors):

    _N_otation [up to 20%]:  incorrect/undefined/ambiguous notation

    _V_agueness [up to 20%]:  incorrect/unjustified/vague claim


1.  [42 marks]

    For each part (a)-(f):

    _C_orrectness [3 marks]:  the CFG correctly generates all strings in
        the language, and only strings in the language
        (give these marks if you can tell that the CFG is correct, even if
        the justification is missing/incomplete; give marks independently
        for each half of the correctness, e.g., a CFG that generates all
        strings in the language but also generates some strings outside it
        should get between 1 and 2 marks, depending on how close it is to
        being completely correct)

    _J_ustification [4 marks]:  convincing argument that the CFG generates
        all strings in the language, and only string in the language.
        This is broken down into 2 parts:
        _Ja_ [2 marks]:  all strings in the language can be generated
        _Jb_ [2 marks]:  only the strings in the language can be generated

    Marker's Comments:

    Regarding correctness, I take 1 mark off for a minor problem, 2 marks
    off for a major problem or many minor problems.
    Missing an epsilon or incorrectly adding one may be minor or major,
    depending on the situation.

    To obtain full marks for justification, the answer needs convince us
    that you know the difference between the two parts, "only" and "all".
    Many people confuse between these and/or mix the arguments together.

    For the "only" direction, you should describe what your CFG can and
    cannot produce, and explain how this does not produce anything outside
    the required language.

    For the "all" direction, you need to mention the characteristics of any
    given string in the language (such as each string can be decomposed
    into blocks of 5 digits for part a), and then explain how your CFG can
    construct this string.


2.  [48 marks]

    (a) [4 marks]

        _F_irst parse tree [2 marks]:  correct parse tree

        _S_econd parse tree [2 marks]:  correct parse tree, different from
            the first

    Marker's Comments:

    You should draw both parse trees to get full marks.  A partial tree
    gets 1 mark off, to be fair to those who draw the whole tree but lose
    marks because their trees are incorrect.


    (b) [4 marks]

        _P_arse tree [2 marks]:  correct parse tree

        _U_niqueness [2 marks]:  convincing argument that the parse tree is
            unique

    Marker's Comments:

    For uniqueness, you can either say that G2 enforces brackets to get the
    other interpretation of the string (unlike G1), or that G2 enforces
    precedence on AND, OR, NOT.
    The following answers are incorrect or too vague, and may lose 1-2
    marks:

    1) "We cannot parse NOT before OR because <expr> can only be expanded
       to '<expr> OR <expr>' or <conj>"
       You can go from <conj> to <pred> then 'NOT <pred>', the point is
       that this requires adding brackets to turn <pred> back to <expr>.

    2) "We cannot parse NOT before OR in G2"
       "G2 does not give us a choice to parse OR or NOT first"
       This is only true for this particular string because it does not
       have brackets, which you should mention in addition to the previous
       statements.

    3) "If we parse 'NOT <pred>' first, we can't produce an OR"
       Same as 1 and 2.  However, the following are accepted because they
       hint at the brackets issue:
       "If we parse 'NOT <pred>' first, we can't produce '<expr> OR <expr>'"
       "If we parse 'NOT <pred>' first, we can't produce '<expr>'"

    4) "This parse tree is unique because
       ...there is no other choice"
       ...there is only one way to get an or-statement"
       ...there is only one way to expand the non-terminals at each step"
       You may be aware of the brackets issue, but you haven't explained
       enough to distinguish your answer from 1, 2 and 3.

    5) "In G2, OR has higher precedence than NOT"
       NOT actually has higher precedence than OR.  If this confuses you,
       think about how how you would draw a parse tree for 2 * 3 + 4.


    (c) [5 marks]

        _S_tring [2 marks]:  correct string (one with multiple parse trees)

        _P_arse trees [3 marks]:  two distinct parse trees for the string

    Marker's Comments:

    The correct string should be of the form
        "<expr> OR <expr> OR <expr>" or "<expr> AND <expr> AND <expr>"
    and you need to provide some specific strings instead of <expr>.


    (d) [2 marks]

        _S_tring [1 mark]:  correct string (cannot be generated by G_1)

        _J_ustification [1 mark]:  convincing argument

    Marker's Comments:

    Many people got this right.  Most trivial examples would work.


    (e) [2 marks]

        _S_tring [1 mark]:  correct string (cannot be generated by G_2)

        _J_ustification [1 mark]:  convincing argument

    Marker's Comments:

    Same as d.  Some people incorrectly give strings of the form
        "<expr> OR <expr> AND <expr> OR <expr>"
    G2 can generate this if you handle the ORs first.


    (f) [11 marks]

        _S_tructure [2 marks]:  clear attempt to argue any string generated
            by G_2 can also be generated by G_1, and reasonable overall
            proof structure

        _I_dea [5 marks]:  correct high-level argument

        _D_etails [4 marks]:  correct write-up of the proof, filling in
            appropriate details where necessary

    Marker's Comments:

    This was quite well done.  To get full marks, you need to show how each
    production in G2 can be "simulated" in G1.


    (g) [11 marks]

        _S_tructure [2 marks]:  clear attempt to argue any string generated
            by G_1 can also be generated by G_2, and reasonable overall
            proof structure

        _I_dea [5 marks]:  correct high-level argument

        _D_etails [4 marks]:  correct write-up of the proof, filling in
            appropriate details where necessary

    Marker's Comments:

    In addition to showing how each production in G1 can be simulated in
    G2, you need to mention the order of derivation if an expression has a
    mixture of ANDs, ORs and NOTs.  This shows us that you understand how
    G2 works, as opposed to the incorrect answer in 2e (see above).


    (h) [9 marks]

        _G_rammar [3 marks]:  correct CFG (unambiguous, equivalent to G_2)

        _C_orrectness [4 marks]:  good justification that G_3 is
            _U_nambiguous and _E_quivalent to G_2 (2 marks each)

        _P_arse tree [2 marks]:  correct parse tree given for string from
            part (c), and justification that is is unique

    Marker's Comments:

    The modified grammar should not change the language -- a solution that
    forces brackets around "<expr> or <expr>" is incorrect.
    To get full marks for justification, you need to explain the reasons
    behind your changes to G2 (i.e., what was problematic about G2), the
    effects of your changes (i.e., why G3 is unambiguous), and that the
    modified productions did not change the language.  This last part is a
    subtle point that many people miss.  The question does hint at this: G3
    is the grammar for L(G2).  On the other hand, a parse tree is not
    explicitly required; a clear description would suffice.


3.  [10 marks]

    (a) [5 marks]

        _I_dea [2 marks]:  correct high-level idea

        _S_yntax [3 marks]:  correct ML syntax
            (if was fine to use if...then...else... instead of patterns)

    Marker's Comments:  (Nothing general.)


    (b) [5 marks]

        _I_dea [2 marks]:  correct high-level idea

        _S_yntax [3 marks]:  correct ML syntax
            (if was fine to use if...then...else... instead of patterns)

    Marker's Comments:  (Nothing general.)


    (c) [5 BONUS marks -- in addition to everything else]

        Be particularly picky for this one, as it is a bonus.

        _I_dea [2 marks]:  correct high-level idea

        _S_yntax and style [3 marks]:  correct ML syntax and style

    Marker's Comments:  (Nothing general.)