*********************
A5 Marking Scheme
*********************
*******************
Q1. James + Johanna
*******************
-(2-5) for an incorrect CFG
-(1-5) per incorrect case
(ex. didn't specify that |vwx| <= p to justify vwx can only contain at most 2 letters)
Additional comments:
Most people correctly got which language was context-free and which was not and most mistakes were small (not enough detail for a case, forgetting a case, ect). Please proof-read! Many of the CFG mistakes looked preventable.
******************
Q2. Molly + Roland
******************
Part one: L is a CFL (out of 10)
-Grammar has very big mistakes: -7
(Eg: can produce a's, b's, or c's out of order)
-Provide PDA but give incomplete analysis of cases: -5
-Grammar produces some strings not in the language: -5
(Eg: strings of the form a^nb^nc^n or the empty string)
-Grammar fails to produce some strings in the language: -3
(Eg: grammar can't produce c or a*b^jc^k with j =/= k)
Part two: L is not a deterministic CFL (out of 10)
-Claiming that the complement of L is {a^nb^nc^n | n >= 0}: -10
-Having the wrong reasoning as to why the complement of L is not context-free
(Eg: claiming that a^nb^nc^n is a subset of the complement of L so the complement of L is not a CFL): -10
-Intersecting complement of L with the wrong regular language or not specifying the language: -5
(Eg: intersecting with (abc)^*)
*******
Q3. Yue
*******
Almost everyone tries to prove this question by considering the regular and context-free language L=(abc)*, some common mistakes that people made are:
-Not giving a explicit formula for perm(L) but only saying it is not context-free: -at most 12
-perm(L) provided is not correct (for example, saying that perm(L)={a^n b^n c^n | n>0} ) -at most 12
-Missing the proof of why perm(L) is not context-free. It is not enough to say “obviously”. -6~8
-Saying the subset of perm(L), {a^n b^n c^n | n>0} is not context-free, then conclude that perm(L) is not context-free. This mistake is the most common one, people should notice that whether a subset of a language is context-free or not does not give any information about the language. To prove that perm(L) is not context-free, using the intersection is recommended (please see the solution), or using the pumping lemma (the proof will be long). -5
Final notes, CFG is not closed under intersection, so the proof using intersection is based on “ the intersection of a regular language and a context-free language is context-free”. However, I did not deduct points if people did not point this out.
*******
Q4. Lin
*******
-claimed not context-free: given 0-5pts depending on the effort shown
-claimed context-free with no explanation given 6pts
-very messy but correct grammar: deducted 3 to 5pts
-close but made a small mistake: deducted 6 to 7pts
-made bigger mistakes or grammar was completely incorrect: deducted 8 to 12pts
Very common mistake was a grammar as such:
S -> ABCDE
A -> aA | e
B -> aBb | e
C -> bCc | e
D -> cDd | e
E -> dE | e
The number of a's and d's are not necessarily matched!
*************
Q5. Florestan
*************
- 4 for giving a CFG without any explanation
- 2 if you mentioned why the string generated by your CFG/PDA were indeed not palindromes but didn't give any kind of explanation as to why one should believe it generated ALL palindromes.
-2 for small mistakes, such as only generating non palindromes of even lengths
-5 for majour mistakes, such as only generating a (small) subset of non-palindromes. A common one was non-palindromes which ONLY differ in one i/n-i position.
To address some common misconceptions, here a few important remarks:
-Deterministic and Non-Deterministic PDAs/CFGs DO NOT have the same computational power. DPDAs/DCFGs are in fact closed under complementation, non deterministic ones are NOT! Because of this, any argument along the lines of "take a non deterministic PDA for L, flip the accept and reject states of that non deterministic PDA to get one for the complement of L" DOES NOT WORK.
-You cannot say that if (L intersect R) = C, where R is a regular language and C is context free, then L had to be context free too. THIS IS FALSE! Take for example the language L= {a^i b^j c^k | i,j,k all different}. This is not context free (but pumpable). Intersect it with R =a*b*, which is regular. You now get C= {a^i b^j | i and j different}, which IS context free.