Welcome! Log In Create A New Profile


Q1 of assignment 4

Posted by hexium 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Q1 of assignment 4
May 11, 2011 02:30PM
Isn't the answer in tut204 supposed to be a TM that will accept ODDPALINDROME?
Looks to me more like it's accepting EVENPALINDROME...


avatar Re: Q1 of assignment 4
May 11, 2011 04:01PM
(a, Y, R)

No edge out of q6... crash

I think it may help to make the lines between q1 q2 q5 q6 a rectangle. Then one sees straight away the a edge going down, and the a edge coming back up. Add the one edge you enter by, and there are always 2n + 1 a's. As far as the number goes it doesn't matter if you branch to b for your next one.

I think it does accept ODDPALINDROME then.

Your Odd machine looks right, too (although one could "play Planarity" with it smile ) Two of the ways to skin this same cat? I suppose that topologically that would mean that in some sense both the graphs are equal. Which is probably too interesting a question to be considering at this hour...

Re: Q1 of assignment 4
May 11, 2011 04:12PM
Problem is, if I give the first tm the string aabbbbaa, which is even, it accepts it (even though it rejects abba). It shouldn't accept any even palindrome. It seems that it accepts some even palendromes (so technically I should probably not try say that it "accepts even palendromes"winking smiley and some odd palendromes, but should only accept odd.
Re: Q1 of assignment 4
May 11, 2011 04:29PM
Whoops, found my problem... Between Q3 and Q4, it should read X,X,L and not X,X,R. I think that sorts out the whole problem and there's nothing wrong then with the answer given in tut204
avatar Re: Q1 of assignment 4
May 11, 2011 05:06PM
Yes, that would do it! OK I was too lazy to try with b's, so never got stuck there, but a glimpse says the pattern is now the same, so should work "recursively".

Interesting that the machines are somehow equal, eh? Of course there are many TMs per language, in all the theorems, but probably if you do the combinatorics MAT course on Y3 level you'd encounter some of the work done on discovering the families of TMs even?
Re: Q1 of assignment 4
May 12, 2011 09:58AM
These TMs remind me of sorting algorithms eye rolling smiley
Sorry, only registered users may post in this forum.

Click here to login