Troy Mark Gonsalves
2004-07-05 17:35:17 UTC
Some of the TAs still have the marking schemes for the questions.
Here's a rough idea of the marking scheme we used...TAs were free to
modify this scheme as needed, and for the most part I'll stand by the
mark they gave you.
The TAs for each question are:
1,4 Jaewook
2 Sherif
3,5 Ibrahim
6 Qi
7,8 Nguyen
You should see the TA if you feel there's been a mistake (except for
question 5). If you not satisfied with the TA's explanation then see me.
1) 3 handling a,b,c properly
2 pushing args on to stack (1 for doing it, 1 for getting the order right)
2 implementing the if and else properly
1 for managing the stack pointer (register 30) properly
2 setting the args correctly
2) I haven't got the marking scheme back from Sherif.
Unfortunately, Sherif did not provide good feedback when marking this
question...many of you have a mark and no explanation of why you have it.
Contact him if you want details. I'll ask him to post the marking scheme
in a moment.
3) This was a 'separater question' (i.e. if you know the material, it's
not that bad, if you 'kinda' know the material it's hard...)
The answer was (and is): a|b(aa|bb|ab|ba)*
That is, all strings of odd length. a|b((a|b)(a|b))* is also correct
You needed to realize that all strings of odd length were acceptable, then
the question was not that hard (if you really know regular expressions).
If you draw a 4 state DFA of this then you'll see that it's almost
identical to a DFA in the notes (expect the accepting states are swapped).
That DFA could be reduced to 2 states (I mentioned this in class) and the
DFA for this question could also be 2 states. Drawing this on the midterm
would not get you marks, but it might have helped you figure out the
question...at least it would have prove (to you) that this was a regular
language.
The marking scheme for this question was (roughly):
-1 for accepting the empty string (not in the language)
-2 for accepting some even strings (not in the language)
-2 for missing some odd strings (all odd strings are in the langauge)
You may have got 0.5 or 1 mark just for trying.
4)
a)
Y 10 10 0010
N must end in a 0 or and even number of 1's
Y 01 1101 with the first half, then 11 from the second
N if we want to use the expression in brackets then the resulting string
must end in a 0...it doesn't, so we can't. This leaves us with 01*10*
which can't recognize the given string.
N Looking at the first half of the RE we can try to simplify it to a+b*a+
That's not necessary but it helps. Anyway, we need to notice that there
is no way to create a string with multiple sequences of b...i.e. we only
have one chance to make b's...the given string has 2 sequences of b's so we
won't recognize it.
N the string starts with an 'a' so we need to start with abb* or ab,
either one will allow us to recognize the first 'ab', leaving 'abababa',
which also begins with an 'a'...meaning we use abb* or ab
again, leaving 'ababa',...we're forced to use either abb* or ab twice
more leaving just an 'a' which can't be matched by abb*, ab or ba.
b) an initial arrow going to an accepting state.
.5 if you were close
if you labeled an edge with an epsilon you got -.5, we asked for a DFA
not an eNFA
c) an initial arrow going to a non-accepting state
.5 if you had something reasonable.
5) Implementing DFA's
I was not happy with the marking for this question. Marks were deducted
for combining tables (which is ok) and for valid pseudocode. I tried to
catch these but may have missed some.
a) 2 transition table
2 actions table
1 accepting table
-.5 for forgetting the Err row and/or 'other' column of the tables.
(unless you alrorithm compensates for this)
Marks were also taken for having the wrong index on your tables.
Should be current state and current input.
if you lost marks for combining the actions and transitions table you
should get them back (come see me).
b) The TA seems to have a very specific idea of what pseudocode is and
took marks from people who have correct algorithms. I think I caught most
of these, but some may have slipped through...if you see blue pen on page
7 or 6 or your exam then you can assume that I've already examined your
solution and given you the mark you deserved.
Marking scheme:
1 for correctly initializing the current state. Initizing to "A" is ideal,
but if you just said "initialize current state to start state" then you
should not have lost marks.
1 looking up the next state using both the current state and the current input
1 lookup and perform the action (not just looking it up)
1 correct return values. You should return r or null. Returning a boolean
was accepting if you mentioned r somewhere in your algorithm (which
suggests that r is stored and accessible after the procedure returns)
1 correct loop condition (until there are no more chars, or while there
are chars, or for each character,...etc.) ...if you lost this mark then
you should get it back.
-1 for getting updating the state before retrieving the action (you need
the current state to retrieve the action)
marks were also deducted for exiting the loop early (i.e. the first time
you encounter an accepting state)...the amount deducted varies
depending on why you exited the loop.
6)
a) 1 mark each for S*, the OR, the concat, the * on everyting, labeling
the final state.
b) in general:
3 marks for creating shortcut edges
1 mark for new accepting states
1 mark for removing e-edges and dead states
more specifically: -.5 for each mistake
c) -.5 for each mistake
7) a) most of you got 3/3
b) 2 parse trees for an ambiguous string...like abaa
c) 4/5 if you accept ab (the original grammar didn't)
8) 6 stack trace (deductions made for missing steps/errors)
2 return value (false)
Here's a rough idea of the marking scheme we used...TAs were free to
modify this scheme as needed, and for the most part I'll stand by the
mark they gave you.
The TAs for each question are:
1,4 Jaewook
2 Sherif
3,5 Ibrahim
6 Qi
7,8 Nguyen
You should see the TA if you feel there's been a mistake (except for
question 5). If you not satisfied with the TA's explanation then see me.
1) 3 handling a,b,c properly
2 pushing args on to stack (1 for doing it, 1 for getting the order right)
2 implementing the if and else properly
1 for managing the stack pointer (register 30) properly
2 setting the args correctly
2) I haven't got the marking scheme back from Sherif.
Unfortunately, Sherif did not provide good feedback when marking this
question...many of you have a mark and no explanation of why you have it.
Contact him if you want details. I'll ask him to post the marking scheme
in a moment.
3) This was a 'separater question' (i.e. if you know the material, it's
not that bad, if you 'kinda' know the material it's hard...)
The answer was (and is): a|b(aa|bb|ab|ba)*
That is, all strings of odd length. a|b((a|b)(a|b))* is also correct
You needed to realize that all strings of odd length were acceptable, then
the question was not that hard (if you really know regular expressions).
If you draw a 4 state DFA of this then you'll see that it's almost
identical to a DFA in the notes (expect the accepting states are swapped).
That DFA could be reduced to 2 states (I mentioned this in class) and the
DFA for this question could also be 2 states. Drawing this on the midterm
would not get you marks, but it might have helped you figure out the
question...at least it would have prove (to you) that this was a regular
language.
The marking scheme for this question was (roughly):
-1 for accepting the empty string (not in the language)
-2 for accepting some even strings (not in the language)
-2 for missing some odd strings (all odd strings are in the langauge)
You may have got 0.5 or 1 mark just for trying.
4)
a)
Y 10 10 0010
N must end in a 0 or and even number of 1's
Y 01 1101 with the first half, then 11 from the second
N if we want to use the expression in brackets then the resulting string
must end in a 0...it doesn't, so we can't. This leaves us with 01*10*
which can't recognize the given string.
N Looking at the first half of the RE we can try to simplify it to a+b*a+
That's not necessary but it helps. Anyway, we need to notice that there
is no way to create a string with multiple sequences of b...i.e. we only
have one chance to make b's...the given string has 2 sequences of b's so we
won't recognize it.
N the string starts with an 'a' so we need to start with abb* or ab,
either one will allow us to recognize the first 'ab', leaving 'abababa',
which also begins with an 'a'...meaning we use abb* or ab
again, leaving 'ababa',...we're forced to use either abb* or ab twice
more leaving just an 'a' which can't be matched by abb*, ab or ba.
b) an initial arrow going to an accepting state.
.5 if you were close
if you labeled an edge with an epsilon you got -.5, we asked for a DFA
not an eNFA
c) an initial arrow going to a non-accepting state
.5 if you had something reasonable.
5) Implementing DFA's
I was not happy with the marking for this question. Marks were deducted
for combining tables (which is ok) and for valid pseudocode. I tried to
catch these but may have missed some.
a) 2 transition table
2 actions table
1 accepting table
-.5 for forgetting the Err row and/or 'other' column of the tables.
(unless you alrorithm compensates for this)
Marks were also taken for having the wrong index on your tables.
Should be current state and current input.
if you lost marks for combining the actions and transitions table you
should get them back (come see me).
b) The TA seems to have a very specific idea of what pseudocode is and
took marks from people who have correct algorithms. I think I caught most
of these, but some may have slipped through...if you see blue pen on page
7 or 6 or your exam then you can assume that I've already examined your
solution and given you the mark you deserved.
Marking scheme:
1 for correctly initializing the current state. Initizing to "A" is ideal,
but if you just said "initialize current state to start state" then you
should not have lost marks.
1 looking up the next state using both the current state and the current input
1 lookup and perform the action (not just looking it up)
1 correct return values. You should return r or null. Returning a boolean
was accepting if you mentioned r somewhere in your algorithm (which
suggests that r is stored and accessible after the procedure returns)
1 correct loop condition (until there are no more chars, or while there
are chars, or for each character,...etc.) ...if you lost this mark then
you should get it back.
-1 for getting updating the state before retrieving the action (you need
the current state to retrieve the action)
marks were also deducted for exiting the loop early (i.e. the first time
you encounter an accepting state)...the amount deducted varies
depending on why you exited the loop.
6)
a) 1 mark each for S*, the OR, the concat, the * on everyting, labeling
the final state.
b) in general:
3 marks for creating shortcut edges
1 mark for new accepting states
1 mark for removing e-edges and dead states
more specifically: -.5 for each mistake
c) -.5 for each mistake
7) a) most of you got 3/3
b) 2 parse trees for an ambiguous string...like abaa
c) 4/5 if you accept ab (the original grammar didn't)
8) 6 stack trace (deductions made for missing steps/errors)
2 return value (false)