I just want to wish everyone luck. I hope to see none of you again :D well at least not in this subject!

Thanks to everyone who helped with the "model" answers, and for the people with questions. Don't think of it as not knowing the answer, think of it as testing if someone else does! It helps everyone learn.

Regards

Rey]]>

a) A function is computable if there exist a Turing Machine that can accept it.

b) As it is accepted by the TM bellow it is computable

]]>

PALINDROME ALAN {a^{n}ba^{n}} {a^{n}b^{n}ba^{n}} {a^{222}} FA NO NO NO NO YES PDA YES NO YES NO YES TM YES NO YES YES YES

Again Yes/No :) ?]]>

i)

Accept(T) = ab(bb)*a

Loop(T) = aa(a+b)*+ ab* + abba(a+b)*

ii) a(ba)*

YES/NO?]]>

i) (be careful of my answer, haven't tested it)

1)Read a,

2)Push X onto stack

3)Repeat 1 - 2 till b is read

5)Read b

6)Read b

7)Pop X from stack

8)Repeat 6 - 7 till Pop /\ from stack

9) Pop X, then Pop X from stack

10)Read a

11)Pop X from stack

12)Repeat 10 - 11 till Pop /\ from stack

13)Read /\

14)Accept

ii) Yes. As 2PDA is equivalent in power to a Turing Machine and a TM is equal to an nPDA (3PDA)

iii) Yes. As above a 2PDA is equivalent in power to a TM.

iv) No. As L is non-context free and PDA only accept context free languages.]]>

WHAT THE HELL DID I MISS HERE! Someone give me a simpler version PLEASE!

Comments:

1. I see that I'm not going to Loop on words starting with 'ab' or 'ba' of even length! Could make an even loop if the first characters did this and make it bounce back and forth. That would add two extra loops above this TM to track these occurrences (above left and right first states)!

]]>

So to show that the language L

Take all nonterminals in the CFG for L

Take all nonterminals in the CFG for L

Now create a new start state S -> S

0. S -> S

1. S

2. X

3. Y

4. S

5. X

6. Y

We have obviously not duplicated any nonterminals therefore these languages should still produce the same language as before.

Proof both ways:

1) All words generated by this new CFG can be generated by either S

So to generate a word we start in S (0) from here we either go to S

2) All words generated by S

To generate a word from L

Waffle Waffle Waffle.]]>

Aaarghh my favorite again, pumping lemmings with length

So lets assume that the L is context free, then by Pumping lemma with length there is some word of sufficient length such that it can be split into five parts uvxyz and can be pumped.

a

should be long enough for us to pump. So by rule one length(vxy) <=2

1) vxy consists of only a's or b's

If we pump the first set a

If we pump the second set b

If we pump the third set a

None of these words are in the Language

2) vxy consists of a's and b's or b's and a's

If we pump the first set of a's and b's it will grow longer than the remaining a's

If we pump the send set of b's and third set of a's they will become longer than the first set of a's

None of these words are in the Language

Therefore proof by contradiction the language L is NOT context free.]]>

Well please could some one tell me if I'm wrong!]]>

a)

Now to translate:

S -> aM | bN

M -> aO | bQ

Q -> aM | bM

O -> aM | bM | /\

N -> aR | bP

R -> aN | bR

P -> aN | bN | /\

Yes/No

b) Convert

S -> Xa | YYa | X

X -> Y | /\

Y -> YaY | a | b

i) Kill /\

S -> Xa | YYa | X

X -> Y | YaY | a | b <-

Y -> YaY | a | b

ii) Kill unit production

S -> Xa | YYa | YaY | a | b <-

X -> YaY | a | b <-

Y -> YaY | a | b

iii) Terminals

S -> XA | YYA | YAY | a | b <-

X -> YAY | a | b <-

Y -> YAY | a | b <-

A -> a

B -> b

iv) CNF

S -> XA | YM | MY | a | b <-

X -> MY | a | b <-

Y -> MY | a | b <-

M -> YA

A -> a

B -> b

Please comment!]]>

a) Well my attempt at the FA

Now the translation:

S -> aM | bN

M -> aO | bO | /\ (a ending)

O -> aQ | bM

Q -> aO | bO

N -> aP | bP | /\ (b ending)

P -> bR | aN

R -> aP | bP

and of course it could be made tidy, but why waste the time. It does what it does. I think!

b)Convert

S -> Xa | Y

X -> aS | aY | bbb | bx

Y -> bY | /\ | a

to CNF

i) boot the /\

S -> Xa | Y

X -> aS | aY | bbb | bx

Y -> bY | b | a <-

ii) kill unit productions

S -> Xa | bY | b | a <-

X -> aS | aY | bbb | bX | a

Y -> bY | b | a

iii) Terminals

S -> XA | BY | b | a <-

X -> AS | AY | BBB | BX | a <-

Y -> BY | b | b <-

B -> b

A -> a

iv) No CNF

S -> XA | BY | b | a

X -> AS | AY | MB | BX | a <-

Y -> BY | b | a

M -> BB

B -> b

A -> a]]>

bit rusty

]]>

I really don't like pumping lemma. REALLY. So help and criticism on this answer appreciated. Would it be worth the marks, did I leave something out? Nit pick people, nit pick!

Assuming that L is context free, then by pumping lemma with length, all words of sufficient length (length(w) > 2

a

Where p is the number of live productions if the language was in CNF. Which should be long enough.

Now lets break the word down so that each vxy

1) Could be all a's or all b's, but if you pump the first a

2) Could be a's and b's or b's and a's. Again pumping the first set of a

So by contradiction of pumping lemma with length the language L is not context free.]]>

So L

The language L

The language L

Now take all nonterminals in L

take all nonterminals in L

So you get

S

S

Now create a new CFG of the combined languages and add the line

S -> S

Obviously the languages have not been changed by the additional sub script, and no duplicate nonterminals have been created. The CFL create by S

Now proof that the CFG is still correct (will fill later):

1) All words in L

2) S generates all words in L

1. Saw something wrong, Short word "ba" got trounced by my # marker.

2. now add 10min onto that

3. Might as well make it 1 hour. Struggling with the loop!

Can someone program this into?:

TM Simulator]]>

1) So read all a's, for every a read, push X onto stack 1. If not a is read n < 1 the 2PDA will crash.

2) After all a's are read/ First b is found (n = stack 1), push 3 more X's onto stack 1 (n+3)

3) For each a that is now read, pop an X from stack 1 and push a Y onto stack 2

4) When stack 1 is empty pop 4 Y's from stack 2 ((stack 1) - 3 - 1)

5) Read all your b's, popping a Y from stack 2 till /\ (stack 2 = empty). If you don't read an b or insufficient b's (n-1) the the 2PDA will crash

6) Read /\ from the tape (tape finished). If tape not empty crash.

7) Accept

ii)

Yes. TM = nPDA and nPDA = 2PDA. The above example is accepted by a 2PDA therefore a Turing Machine, therefore a 3PDA (nPDA)

iii)

Yes. 2PDA = nPDA = TM. (This seems a bit short)

iv)

No. As PDA < nPDA = TM. PDA only accept context-free languages, and this is a non-context free language

YES/NO]]>

b)(Do you draw a TM?)

1. Get first a replace with A

2. Go to end of tape add X

3. Return to First A move one right and replace a with A

4. Repeat 2-3 until no more a's/ first X

5. Goto beginning of Tape

6. Replace all A's with a's and X's with a's till end of tape

7. HALT

TM = Computable

YES/NO?]]>

Updated! Read bellow.

1)

(a)Regular -> (b)Context Free -> (c)Recursive -> (d)r.e

2.a) (a+b)*ab

b) {a

c) L <- is this right?

d) MATHISON

As in the book p574]]>

Accept(T) = a(aa)*b

Loop(T) = a(aa)*ba(a+b)* (Correction read bellow)

Does anyone have a copy of the previous exam (2009 or 2008)?

Thanks]]>

This does not seem to me like a valid CWL, since there seem to have slipped an extra caracter in there. Anyone else had this problem?]]>

Actually writing a compiler would be fun, especially to see how context free grammars are applied and what is involved.

Does UNISA have any courses where you would actually do that?]]>

Am I correct in my understanding?

I'm just wondering if there is a simpler way to do this. Maybe implement the algorithms in code and let the computer solve the problem :)

I wish I had time to try that.]]>

I just want to know if there's someone in the same boat as i am since i haven't received my results back and

need this to secure exam admission.

Thanks

8-)]]>