Q1 of assignment 4

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

Even:

Odd:
 Re: Q1 of assignment 4 May 11, 2011 04:01PM Registered: 10 years ago Posts: 3,496 Rating: 1
aa#
(a, Y, R)
Ya#
(a,a,R)
Ya#
(#,#,L)
Ya#
(a,X,L)
YX#
(Y,Y,R)
YX#

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

a
A#
A#
halt.
 Re: Q1 of assignment 4 May 11, 2011 04:12PM Registered: 11 years ago Posts: 111 Rating: 0
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" and some odd palendromes, but should only accept odd.
 Re: Q1 of assignment 4 May 11, 2011 04:29PM Registered: 11 years ago Posts: 111 Rating: 0
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
 Re: Q1 of assignment 4 May 11, 2011 05:06PM Registered: 10 years ago Posts: 3,496 Rating: 1
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 Registered: 11 years ago Posts: 111 Rating: 0
These TMs remind me of sorting algorithms
Sorry, only registered users may post in this forum.