Reformulated proofs

Hi Guys,

Hope everyone is winning with exam preparations!

I was just wondering if anyone had examples of the reformulated proofs that the study guide talks about. Its great that they don't agree with Cohen and provide a better proof, but kind of pointless if we don't know how to apply it. I always find that the examples help me understand what the proof actually does!

Any thoughts on this?

Hi,

Which reformulated proofs are you referring to, the following?

1) CFG's are closed under Kleene star
2) Context free languages are closed under product
3) Context free languages are closed under union

2) and 3)

I don't know about the "reformulated" proofs but I think those proofs in the textbook are pretty clear.

Yeah thats just the problem - the ones in Cohen do make sense, as they provide examples, but in the study guide they say that they don't agree with all of Cohens proofs and that we should use the reformulated proofs that they provide instead.

Are you sure you're not getting mixed up. In chapter 6 of the study guide which relates to chapter 17 of Cohen which is where the union, product and Kleene closures are defined but there are no reformulation of any othe Cohen theorems. In the following chapter of the study guide then refer to reformulation of proofs for emptiness (theorem 42) and membership a.k.a. CYK algorithm (theorem 45). As far as these two "reformulated" proofs are concerned, my thinking is that both these AND the Cohen approaches should be accepted because both work and result in the same answer.

See quote from study guide (chapter 18 - Decidability. At the end of the first paragraph) ... "We are going to reformulate two of the algorithms. You should follow these steps when required to execute one of these algorithms". So yes, I agree that the will result in the same answer but if you have to show the steps, they will be different, won't they? If they don't give marks for showing the steps then I'm sure its fine.

I did see that note but even if the steps differ in some way and the proof still makes logical sense and the answer is still the same, how can they deduct the marks?