Test 3  Comments
by Tim Paterson (only marker)



Throughout the test, I deducted 1 or 2 marks for minor details, so if
you lost 1 or 2 marks it means that you had a correct solution that
had
some small element either wrong, or not specified.

Question 1:

Most people got this question right.

Question 2a:  

Many people tried to convert to a grammar first, which is the wrong
way
to approach the question.  There may be variables that are not
reachable/usable, but that doesn't mean that the states they represent
are unreachable (because the variables correspond to the PDA
travelling
from one state to another).  That is, state p might be reachable, and
state q might be reachable, but q might not be reachable from p and so
A_pq is a useless variable.

Others tried a marking algorithm.  However, if no mention was made of
how the stack pushes and pops were ensured to be consistent then no
marks were awarded (in that case it's just a DFA, and the question
specifically talked about PDAs)

2b) and 3)

All of the problems on these questions essentially boil down to
improper or non-existent reductions.  To properly reduce language A to
language B, we need (for each instance a of A) an instance b of B such
that b is in B if and only if a is in A.  It is not enough to just
test
some TM for membership in language B and conclude that if we could
decide B we could somehow therefore decide A.

Rice's Theorem doesn't apply to the language in 2b) because the second
requirement of Rice's Theorem requires that the property be dependant
on the language of the candidate TMs.  The property of having a
useless
state is not language dependant (because if M is a TM with no useless
states, construct M` with one extra unreachable state.  Then one
machine is in U_TM and the other is not, but L(M) = L(M`))

4) 

Mostly the problems with this question were improper or non-existance
reductions from PCP to AMBIG_CFG.  Some students were on the right
track, but failed to give a candidate grammar G, in which case part
marks were awarded.

5)

Generally people either completely got this question or completely
missed it.  5 marks were deducted if f(w) was given as <M,w> but M was
not identified as a recognizer for B.  10 marks were deducted if M
wasn't identified as a recognizer for B and if some other TM R_B was
identified as a recognizer for B.  5 marks were awarded for some good
insight into the problem in some cases, even if the solution was
incorrect.