Email me on 45755124@mylife.unisa.ac.za or reply to this post.]]>

May I ask for past material for the following subject, I will be taking these modules in 2012. Please kindly send to sedeya@gmail.com

(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.

Regards

Rutendo.]]>

my thoughts herewith on the question 3 for pumping lemmas in 2006 exam paper.

They ask to prove that a

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) > 2

thus we can apply the pumping lemma and thus the word w can be devided into uvxyz (5 parts) such that uv

such that

length(x) > 0

Length(v) + length(y) > 0

Length(vxy) <= 2

i choose

i choose n to be 2

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 2

after pumping this value will no longer be the same, because the first 2

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 a

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.

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.

IF USEFULL and SELF EMBEDDED then L = INFINITE

Missing anything]]>

If anyone has past papers or other useful information about this module please mail it to me at roderick.midgley@gmail.com.]]>

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.]]>

I know there are videos on Youtube uploaded by CoderIsland that are useful to this subject.

Can somebody tell me which ones they are?

Thanks]]>

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:

java.lang.NullPointerException

when clicking on official Study Material link...

still awaiting reply from myunisa support...]]>

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]]>

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]]>

thanx]]>

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!

34177531@mylife.unisa.ac.za]]>

But all went well.]]>

Just relax, its going to be fine.]]>

Even:

Odd:

]]>

P = "G is CFG .AND. w is in G with len(w) > 2

Briefer form of P: "If (ANY) w is long enough ..."

Q = "w must split somehow into uvxyz PLUS uv

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

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

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.]]>

2.Can a FA and a PDA accept the following? a^n b a^n, a^n b^n b a^n]]>

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

]]>

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

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

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.]]>

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

Hope you can give some ideas.]]>

]]>

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?]]>

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 L

S -> S

S

X

Y

S

X

Y

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

--

Brad]]>