cos301 exam

Hi Guys
I've just written the exam and no problems with the questions. Pretty much standard but did anyone struggle to complete the paper? I really battled with the time and could have used an extra half hour at least.

Hey there!

Just so happy to be done!
Time was not an issue, but got totally stuck at the drawing of the TM, the rest of it was fine!!!

The exam went well i must say, except, as Shirley said, very long. I wrote and only had 10min to check that i've done everything, no real time to check for mistakes or anything. What did you guys get for the Accept(T) and Loop(T) outputs?

I couldn't have done the last qst on the unary encoding without your help here (to all that contributed, especially iva). Thanks guys! PS, since n >= 4, did you guys also start with 4 a's in the front before doing the rest?

i agree you didn't really get time to think abotu stuff , that unary one i read to the end of the string and traced back removing the last 4 a's (a,delta,L)

Hi

I would have loved to have an extra 15 minutes to get my TM perfect.

For what it is worth, here's my try:

Q7
Accept(T): All words from (a + b)* of odd length that starts with a single a, have odd number of b's and ends with an a.
Loop(T): All words from (a + b)* that starts with more than one a.
Output: ab(ab)*a

Q9
Started with 4 a's as well

This was my last exam, hopefully I can call myself a graduate in a month or so. Good luck to all with the results!

Yip, that's similar to what i had, i also started with 4 a's, then skipped through any other a's, then after lambda, removed last 4 a's.

I don't understand the 2 hour exam though for a 3rd year module. We had to draw 4 machines and the rest basically consisted of proofs, so much to do in so little time!

Goodluck Jan, you are so lucky, i still have 10 modules before i'm done

I did the same as Iva.

Anyhow guys I don't want to think about it too much.

It's over!!!! That was my last & hopefully I will have my degree come Dec 11. Good luck to everyone! And thanks to all that took part in the forums - it made it seem a little less lonely.

Cheers!

I couldn't finish in time and had to leave out the second part of 6 (proof both ways).


For the unary one I changed the first a to A to ensure I don't go left over the first a.

JanUys Wrote:
-------------------------------------------------------
> Q7
> Loop(T): All words from (a + b)* that starts with
> more than one a.

If you had an a after two b's you would also loop.

jeanbodemer Wrote:
-------------------------------------------------------
> JanUys Wrote:
> --------------------------------------------------
> -----
> > Q7
> > Loop(T): All words from (a + b)* that starts
> with
> > more than one a.
>
> If you had an a after two b's you would also loop.


Correct

This exam was a breeze. Finished in 1h15m. Just had to redo my TM twice because the page got too messy. Reckon I nailed an A for this. Now if I managed to pass that horrible COS351 exam I'll have my degree. No more sacrificing weekends for me!

Annie Wrote:
-------------------------------------------------------
> Yip, that's similar to what i had, i also started
> with 4 a's, then skipped through any other a's,
> then after lambda, removed last 4 a's.
>
I have to ask - why even count the first four a's ?
The question stated that n >= 4.

--
Learn something new - updated weekly

Hello all

I am a little disappointed - in 2 hours it is not possible to
properly test a module such as this; no questions tested any
theory from the chapter that introduces the halting problem,
which is unarguably the most important concept in computer science
(that a TM can accept another TM as input, or generate TM
as output, etc)?

Where were the questions that tested the second most important
concept - Churches Thesis? No one would call someone who could
not explain, use and/or prove those concepts a "computer scientist".

Instead we get to draw a TM for "f(n) = n - 4 | n >= 4", which
should be trivial. We get asked to prove that a given language
is not a CFL /with length with all the definitions given/ when
anyone who understands the theory should be able to put forward
a logical argument for why the language is not a CFL (without
length, for example).

We got asked the simplest questions possible in each category
(the simplest possible PDA, etc).

Oh well, hopefully I passed.

jeanbodemer Wrote:

------------------------------------------------------------------------------

> I couldn't finish in time and had to leave out the second part of 6 (proof both > ways).


It might be your lucky day, did you notice the mistake in Question 6 of the paper?

The English question asked for union (L1+L2) and the Afrikaans one asked for product (L1L2).

I did write a note in the paper but I just hope they notice before they get to my paper...

Jip, I also put a note in my exam paper. (about the L1L2 and L1+L2) Can we get full marks for the questions, or is that pushing it.

I have to agree with goose. A two hour paper is not sufficient to test a person on the content. With that being said I feel as thou my actual mark will not reflect my knowledge of the subject. At least my 10% for the assignments will help.

Would it realy, REALY make a difference if the paper was 3 Hours? To me it should be 3 hours. I didn't finish in time, and thats without attempting the pumping lemma question. I couldn't even test my TM properly.

BTW: IF computability is defined using a TM, and TM = 2PDA (or nPDA) then surely we can define cumputablity in terms of a 2PDA as well? (I didn't in the exam, but surely it can be done?!?)

Oh, and how easy was that table with the YES and NO answers.

goose Wrote:
-------------------------------------------------------
> I have to ask - why even count the first four a's
> ?
> The question stated that n >= 4.


Cos when you reach the end, you trace back and start deleting 4 a's, if you don't find 4 a's i.e. (a,delta,L), the system crash. I would assume the TM would then be incorrect for the function?

It would be easier just to delete the first 4 a's. Mind you I didn't do it like that, I only realised it after the exam.

I made my own life difficult by making the first a an A to ensure I didn't go past the beginning of the tape. But then I had to find it at the end and change it back to an a. Real bright!

Annie Wrote:
-------------------------------------------------------
> goose Wrote:
> --------------------------------------------------
> -----
> > I have to ask - why even count the first four
> a's
> > ?
> > The question stated that n >= 4.
>
>
> Cos when you reach the end, you trace back and
> start deleting 4 a's, if you don't find 4 a's i.e.
> (a,delta,L), the system crash. I would assume the
> TM would then be incorrect for the function?

You would always find 4 a's, the question stated that n
is greater than or equal to 4, so there is no
point in ensuring that there are at least 4 a's.