*********************
A4 Marking Scheme
*********************
***********
Q1. Roland
***********
Part 1 Mistakes:
Most people had no trouble with this question.
-Some people only used examples to answer the question: -5
-When doing induction, some people used wrong cases: -3
-When doing induction, some people didn't mention the case when the rule S -> SS is used: -2
-Some people used examples to justify important parts of the question: -2
-Using induction, then starting analysis from the leaves of the production tree: -2
-When analysing the productions, not addressing how left parentheses always preceed right parentheses: -2
-Small misunderstandings (e.g. saying in the rule S -> SS must produce the same string): -1
-Claiming that w = (x)y and y must be a non-empty string: -1
Part 2 Mistakes:
The two most common mistakes that people made are marked with * and **.
-Only giving a high-level description of a solution: -10
(e.g. "Use the rules recursively to build any string")
-*Not justifying why every balanced string is of the form w = (w') or w = w'w": -7
-Not justifying other important claims: -7
(e.g. Given a balanced string with n pairs of parentheses, there are only 2 ways to add parentheses while
maintaining balance)
-**Saying that if w = (w'), then w' is also a balanced string: -5
-When doing induction, some people used wrong cases: -5
(e.g. Many people had the following cases: w = (w'), ()w', or w'())
-Some people used examples to justify important parts of the question: -5
-Saying that the first and last parentheses must be paired: -2
-w = (x)y and thinking that y must be non-empty: -1
-Base case does not include the empty string: -1
********
Q2. Yue
********
Almost everyone gets correct answer for this problem, but some people who expanded more than one variable at a time (for example, writing “aaSbS->aab” or “aS->aaSb” without any other explanation) will lose 1 or 2 points. Besides, since unambiguous grammars can give different derivations just by altering the order in which non-terminals are expanded, anyone who gives two different derivation sequences that correspond to the same tree will only get 5 points.
********
Q3. Lin
********
Note: I was fairly lenient given the confusion between acceptance by state vs acceptance by empty stack.
Comments about common errors or misunderstandings:
-An epsilon, epsilon -> epsilon move from a state to itself is absolutely useless (a surprising number of students did this). While many students seemed to be aware of this, I just wanted to note that two states with bidirectional e, e->e moves between each other can be merged into one state (this is also extendable to more states).
-When accepting by empty stack, the start/end of string stack symbol (usually $) is not necessary (no deductions for this). However, it cannot be assumed that some "start of stack" symbol rests at the bottom of the stack by default (some solutions only popped $ without pushing it anywhere).
-The problem statement did not mention any symbols in the alphabet besides {(, ), [, ]} ! Some people included additional symbols for "words" inside the brackets. No points were deducted here as long as the inclusion of these symbols did not affect the validity of the PDA.
-About stack manipulation, a -> b means that you pop a, then push b. Some people seemed to interpret it as "if a is at the top of the stack, push b". There is no peeking, only pushing and popping. Also, you can't "double push". Some solution included transitions of the form [, (-> ([. This does not mean you're pushing ( then [, but that you are pushing "([" as a single symbol to the stack.
Deductions for most common errors:
did not accept empty string (acceptance by state only) -2
did not accept nested brackets, e.g ([]) -3
misuse of $ symbol -2
described stack manipulations correctly with no mention of state transitions (you need to tell me that you're working in a single state) -1
misunderstanding of stack transitions -2
**********************
Q4. James + Florestan
**********************
15 for the CFG:
6pts per case (n<=p and m<=p)
3pts for basic understanding of CFG (basically free points for attempting the question)
-2 pts for small mistakes ( Example: Missing Epsilon reproduction on a rule
Don't catch that p can be 0 if n or m is 0, i.e. b* and a* are in the language)
-4 pts for larger mistakes ( Example: M -> bMc | A instead of M -> bMc | e)
5 for explanation:
1pts for explanation which is too short / incomplete.
3pts if missing either direction but cover one direction 'well'.
5pts for a complete explanation
-1 for mistakes in reasoning
************************
Q5. a) Molly b) Johanna
************************
a)
Most people get this question correctly, Some common mistakes will loss mark are:
1 missing start symbol -1
2 Did not discuss the final states of the DFA or the construction of terminals in the CFL would not work correctly -1~3
3 When discuss the transition function, the corresponding CFL gramma fails or the construction is not clear enough -2~5
4 other typo or minor mistake -1~2
One important thing is some students draw a specific DNF and construct a CFL for that DFA without further explanation. This will cause an automatic 0. That's not proving the problem.
b) This question was out of 10.
A lot of people got 0 for not using the definition given!
0 was also given if the claim was tried to be proven true, the grammar given was completeley wrong, or the explanation for why it was false was totally wrong.
6 points if only the non-regular language was given with no corresponding linear grammar.
7-9 points were given if there were mistakes in the grammar (depending on how severe).
Final notes, a few people also tried giving a grammar that produced the language which contained {a^n b^n | n >= 0} as a subset and claimed this was a counterexample. You must prove that the entire language is not regular, not just a subset!