School of Computing Forums - COS301Y Theoretical Computer Science 3 Sun, 18 Aug 2019 10:02:47 +0200 Phorum 5.2.18,160538,160538#msg-160538 Book for sale (no replies),160538,160538#msg-160538 SOLD

Email me on or reply to this post.]]>
Mona COS301Y Mon, 12 Dec 2011 20:31:28 +0200,160218,160218#msg-160218 Exam Results (6 replies),160218,160218#msg-160218 sly_fox COS301Y Tue, 13 Dec 2011 11:51:51 +0200,159991,159991#msg-159991 Past Material (1 reply),159991,159991#msg-159991
May I ask for past material for the following subject, I will be taking these modules in 2012. Please kindly send to

(COS2621) Computer organization (Computer Science 221)
(COS2661) Formal logic 2 (Computer Science 261)
(INF3705) Advanced systems development (Information Systems 305)
(COS3701) Theory of computer science 3 (Computer Science 301)
(COS3711) Advanced programming (Computer Science 311)
(COS3721) Operating systems and architecture (Computer Science 321)
(COS3712) Computer graphics (Computer Science 340)
(COS3761) Formal logic 3 (Computer Science 361)

Thanks in advance.


roots COS301Y Tue, 22 Nov 2011 18:21:56 +0200,158113,158113#msg-158113 Exam paper 2006, pumping lemma, my answer (2 replies),158113,158113#msg-158113
my thoughts herewith on the question 3 for pumping lemmas in 2006 exam paper.

They ask to prove that an b an+3 bn-1 is NON CONTEXT Free

So we put down the whole assumption of L is context free and thus has a CFG in CNF with p live productions and a word w with length(w) > 2p
thus we can apply the pumping lemma and thus the word w can be devided into uvxyz (5 parts) such that uvnxyz is also in L

such that

length(x) > 0
Length(v) + length(y) > 0
Length(vxy) <= 2p

i choose

i choose n to be 2p, thus each exponent n will be such (sorry dunno how to format exponent on exponent in this editor)

NOw we take this options where vxy might be.

1. It might be in a single clump of a or b
if so and if then pumped to vvxyy or more, a will be increased at one clump, but not in the others. This would result in the relationship between the first a and the second a to become null and void.
in other words before pumping we had a value of n / n+3 (or rather 2p / 2p + 3
after pumping this value will no longer be the same, because the first 2p would become (2p)n where n is the number of times pumped.
Same wouldf apply to any of the other clumps.

2. THe other option is the vxy falls over part of a's and part of b's (straddles as the book says). If so, taking the first two sets of a's and b's, when pumped it would increase either the a's or the b's or both. Again messing up the value relantioship between these a's and b's and the others.

hence all cases are contradictory to assumption.

Does this make sense.?

it seems easier with anbndncn]]>
dve83 COS301Y Mon, 24 Oct 2011 06:25:50 +0200,158109,158109#msg-158109 Theorem for INFINITE LANGUAGE OR NOT (no replies),158109,158109#msg-158109
just have some thoughts / questions on the first part of the work. you might find another post after this touching on other topics.

please give your input.

The Theorem that allows you to see if language is finite / infinite:
My understanding according to theorem 43 and 44.

0. make sure is isn't nullable, byt reverse working the NULL sign to see if S ever gets to NULL. Question: if its NULLABLE, what does this mean? surely there are ways to make S -> Null, but that doesnt mean we dont have other ways of generating words.
1. make sure its in CNF
2. remove unproductive terminals (ones that dont go to nonterminals ever -- ie. N =>* n - it will never reach n)
3. Find the useful ones by blue paint. The we know which Non terminals take part in forming words. Remember the useful ones;
4. show that the useful non terminals are actually usefull by substitution
5. Now mark each of the useful NON Terminals as FUNNYX, and see if its self embedded.


Missing anything]]>
dve83 COS301Y Sat, 22 Oct 2011 16:17:12 +0200,157777,157777#msg-157777 Past Exams and Other Relevant Info (no replies),157777,157777#msg-157777
If anyone has past papers or other useful information about this module please mail it to me at]]>
SmokingToe COS301Y Tue, 18 Oct 2011 20:40:28 +0200,157574,157574#msg-157574 Chapter 17 - CLosure under +, . and * (2 replies),157574,157574#msg-157574
Its seems pretty easy to show that a language(s) L1 and L2 are closed under +, product and * (kleene closure),

but in our 2006 exam paprer they ask

1. Show the language L1L2 and
2. prove that it is correct (two way proof).

I need to know what they want from number 2. The number 1 is the proof in Cohen.]]>
dve83 COS301Y Fri, 21 Oct 2011 00:56:09 +0200,157273,157273#msg-157273 Assignment 2 question 1 (2 replies),157273,157273#msg-157273 lhristov COS301Y Sun, 23 Oct 2011 04:04:50 +0200,156924,156924#msg-156924 CoderIsland videos (2 replies),156924,156924#msg-156924
I know there are videos on Youtube uploaded by CoderIsland that are useful to this subject.
Can somebody tell me which ones they are?

TraceyB COS301Y Mon, 17 Oct 2011 09:07:00 +0200,156812,156812#msg-156812 myUNISA (1 reply),156812,156812#msg-156812
get the following
Fatal internal error handling request:
Target exception of class java.lang.NullPointerException
Successive lines until stack trace show causes progressing to exception site:


when clicking on official Study Material link...

still awaiting reply from myunisa support...]]>
dve83 COS301Y Tue, 04 Oct 2011 16:21:50 +0200,151878,151878#msg-151878 Theoretical Computer Science Tutorials (no replies),151878,151878#msg-151878 based in PTA hub about tutorials and she responded that they need a minimum of 5 student to arrange tutorials for them, she also mention that usually they don’t offer tutorials for third years but if students need assistance they have to indicate so that they can be helped.

Now my proposal is: can you please indicate if you need tutorials so that I can get back to that lady with a number of those who need help like me. The sooner ,the better. its only R150 to enroll for tutorials per 3 modules.

thanks]]> COS301Y Mon, 25 Jul 2011 09:13:44 +0200,151837,151837#msg-151837 Second Semester Assignment 1 (5 replies),151837,151837#msg-151837
got a question:

when removing unit productions and we have

S --> A
A --> B | b
B --> a

I can easily understand that to remove the unit productions we get

S --> A gives S -> b thus removing S--> A
S --> A --> B gives S --> a thus removing S --> A --> B
A --> B gives A --> a thus removing A --> B

result is:

S --> b | a
A --> a
B --> a

but the assignment has something like this

S --> AA
A --> BB | B
B --> a

what do I do with the AA..?

should I go S --> AA gives

a) S --> B and thus a
b) S --> BB and thus aa

is this correct?

and what if B also --> aa? then a and b above should include all combinations S-->B (thus a | aa) and S --> BB aa | aaa | aaaa

sorry hope this makes some sense, I just need to know if what Im doing is correct, the example in the book doesn't do S -> AA types.

thanks in advance for any guidance]]>
dve83 COS301Y Mon, 25 Jul 2011 11:15:42 +0200,149524,149524#msg-149524 Results are out! (1 reply),149524,149524#msg-149524 hexium COS301Y Mon, 25 Jul 2011 11:02:39 +0200,148696,148696#msg-148696 Tutorial letter (no replies),148696,148696#msg-148696

sly_fox COS301Y Mon, 30 May 2011 21:20:32 +0200,148198,148198#msg-148198 Assistance required! (no replies),148198,148198#msg-148198
pls can someone email me the tut letters and whatever solutions are available asap, my internet access is severely limited at the moment.

Thank you kindly!]]>
quaker COS301Y Thu, 19 May 2011 09:36:29 +0200,147618,147618#msg-147618 Exam Post-mortem (12 replies),147618,147618#msg-147618
But all went well.]]>
BlaXpydo COS301Y Mon, 30 Jan 2012 13:00:14 +0200,147581,147581#msg-147581 Exam (4 replies),147581,147581#msg-147581
Just relax, its going to be fine.]]>
BlaXpydo COS301Y Sat, 14 May 2011 14:56:26 +0200,147503,147503#msg-147503 Question 9 (3 replies),147503,147503#msg-147503 BlaXpydo COS301Y Wed, 11 May 2011 20:37:31 +0200,147470,147470#msg-147470 Q1 of assignment 4 (5 replies),147470,147470#msg-147470 Looks to me more like it's accepting EVENPALINDROME...


hexium COS301Y Thu, 12 May 2011 09:58:39 +0200,147468,147468#msg-147468 Pumping Again (2 replies),147468,147468#msg-147468 ==========

P = "G is CFG .AND. w is in G with len(w) > 2p"
Briefer form of P: "If (ANY) w is long enough ..."

Q = "w must split somehow into uvxyz PLUS uv2xy2z must also be in G"
Briefer form of Q: "then w pumps."

Theorem's form: P -> Q

Equivalent to this is the contrapositive: ~Q -> ~P

That means you can take w -fails-Q and conclude ~P. You can prove a NEGATIVE.


Now I get a bit tangled up on what we have to do to w sometimes, and I think I may be onto why. It's because you prove that one word is an exception to Q. This one single chosen word doesn't pump, and since the theorem says every word must pump, you've supplied the necessary "exists" to refute that "forall".

Great. But then you go about this "exists" proof in a sort of "forall" kind of way. You only need to find one exception, but to find that exception the (one) word you reckon will fail must fail no matter what arrangement you try. That's what I mean in a Kind Of "forall" way. You have to cover Every possibility.

You're trying to prove a single "exception to the rule", but you have to do that by covering all the cases.

Put that way, there's nothing particularly difficult about it. Maybe when a bit of this kind of confusion kicks in just remember "all-cases is not all-words".

The "forall" is an illusion. It's only KindOf ...


The with-length version of the theorem is easier. All it does is give you more ways of proving your exception.]]>
slow_eddy COS301Y Wed, 11 May 2011 20:33:59 +0200,147402,147402#msg-147402 Random Question (3 replies),147402,147402#msg-147402
2.Can a FA and a PDA accept the following? a^n b a^n, a^n b^n b a^n]]>
BlaXpydo COS301Y Wed, 11 May 2011 11:32:16 +0200,147152,147152#msg-147152 Q9 2006 (1 reply),147152,147152#msg-147152 prove the function f(n) = n + n n >= 0

is computable, use unary encoding. The remarks in tutorial letter says to use a TM. Is this answer just by drawing the TM enough?

35994908 COS301Y Sat, 07 May 2011 18:33:26 +0200,147140,147140#msg-147140 2006 Q7 (3 replies),147140,147140#msg-147140
Here is my answer for Question 7. It feels to short for 7 marks, but I do believe it is correct.

The TM will only accept a langauge of one or multiple a(s) followed by one b, thus a+b
The TM will loop on any a langauge of one or multiple a(s) followed by one b and then one or multiple a(s), thus a+ba+b*]]>
d-_-b COS301Y Sun, 08 May 2011 23:46:11 +0200,147138,147138#msg-147138 2006 Q6 (3 replies),147138,147138#msg-147138
This is my attampt at Question 6. I do believe it is correct, but you know what they say about assumption...

Question 6

(i) I will create a loop that push all the a(s) into stack 1 and stack to until a b is read.
Then I will push 3 extra a(s) into stack 1 and pop one a out of stack 2.
I will then for each a that is read pop a a from stack 1 until I read a b and then make sure stack 1 is empty.
I will then for each b that is read pop a a from stack 2 until I read a empty character and then also make sure stack 2 is empty.

(ii) Yes, because a PDA with 2 or more stacks can accept any language.

(iii) Yes, because a 2 stack pda is equivalent to a TM.

(iv) No, because a PDA can only accept context-free languages.]]>
d-_-b COS301Y Sat, 07 May 2011 16:56:27 +0200,147134,147134#msg-147134 Q3 2006 (6 replies),147134,147134#msg-147134 BlaXpydo COS301Y Sat, 07 May 2011 18:26:50 +0200,147115,147115#msg-147115 Q8 2006 (5 replies),147115,147115#msg-147115 Recursively enumerable languages and Recursive languages?

I'm actually a bit short on knowlege on this part, can't really remember what is what.

Hope you can give some ideas.]]>
BlaXpydo COS301Y Mon, 09 May 2011 21:29:04 +0200,147097,147097#msg-147097 Assignment 2 (3 replies),147097,147097#msg-147097 BlaXpydo COS301Y Fri, 06 May 2011 14:08:27 +0200,147032,147032#msg-147032 Q5 2006 (8 replies),147032,147032#msg-147032
35994908 COS301Y Fri, 06 May 2011 22:37:03 +0200,146893,146893#msg-146893 Chomsky Normal Form conversion process - Why is the order crucial? (1 reply),146893,146893#msg-146893
In tutorial letter 102 on page 9 it tells us the 3 steps how to convert a CFG to CNF, at the end it states: (Make sure that you understand why the order is crucial).

I can try to do it in the wrong order and see that it will be harder or impossible to convert a CFG to CNF and I will also reread the chapter in Cohen book.

But I also thought I would just ask the internet, so anybody that knows the answer?]]>
d-_-b COS301Y Thu, 05 May 2011 12:55:49 +0200,146872,146872#msg-146872 Q4 2006 (3 replies),146872,146872#msg-146872 S -> XY | b
X -> aX | bY | a
Y -> aX | bY | b

CFG 2:
S -> SY | X
X -> bS | bX
Y -> a | aX | ^

Write down a grammar that will generate L1L2:

S -> S1S2
S1 -> X1Y1 | b
X1 -> aX1 | bY1 | a
Y1 -> aX1 | bY1 | b
S2 -> S2Y2 | X2
X2 -> bS2 | bX2
Y2 -> a | aX2 | ^

Question: How do you prove this in both directions (i don't know what that means)?

35994908 COS301Y Wed, 04 May 2011 21:34:55 +0200