Welcome! Log In Create A New Profile

Advanced

Oct 2006 Exam Question 5.

Posted by ian.coetzer 
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
Oct 2006 Exam Question 5.
November 02, 2009 02:34PM
Hi,
Please send me an example of Oct. 2006 Exam question 5.
It has stumped me!

thx
Re: Oct 2006 Exam Question 5.
November 02, 2009 02:44PM
Join the club smiling smiley
Re: Oct 2006 Exam Question 5.
November 02, 2009 03:14PM
Oh no!
Yup I spent this whole morning trying to find a way to do this one on a whole bunch of papers, my study is a mess right now thanks to that question.
I came so close a couple of times but then found out that my tests failed.

Should we not try and simplify this one by writing for example a "#" in the beginning and wherever we read a consecutive ba make the second letter A,
thus we will end up with a tape looking like this 'during' processing (since I don't know how to successfully halt this beast).

X......bA.......bA.....bA

I know that the PDA will have to perform the following

Accept: (aa + ab + bb + ba)* ba

Loop: (a+b)*(ba)(a+b)*(ba)(a+b)* < actually not sure of how this must look except that it must contain:

(odd number of characters or null) (ba) (odd number of characters or null) (ba) (odd number of characters or null)
but this ends up being even if (ba)(ba) only exists .... aaaai bugger.
Re: Oct 2006 Exam Question 5.
November 02, 2009 04:55PM
Yip, that's exactly why I stopped wasting my time on it. I think there must be a mistake in the question somewhere otherwise this is the most difficult machine we've had to draw all year and once you've figured out the "trick" it becomes solvable. I'm not wasting another minute on it and rather focusing on understanding everything, hoping the lecturers haven't thrown such a difficult machine into the paper.
Anonymous User
Re: Oct 2006 Exam Question 5.
November 02, 2009 08:51PM
Even words and odd length words are obviously mutually exclusive, so "accepted" words and "loop-forever" words can't mix on this very basic level.

The 1st accepts include
ba aaba abba baba bbba aaaaba aaabba aababa aabbba abaaba ababba abbaba abbbba baaaba baabba bababa babbba bbaaba bbabba bbbaba bbbbba

The 1st loop-forevers include
ababa baaba babaa babab babba bbaba aaababa aabaaba aababaa aababab aababba aabbaba abaaaba abaabaa abaabab abaabba ababaaa ababaab abababa abababb ababbaa ababbab ababbba abbaaba abbabaa abbabab abbabba abbbaba baaaaba baaabaa baaabab baaabba baabaaa baabaab baababa baababb baabbaa baabbab baabbba babaaaa babaaab babaaba babaabb bababaa bababab bababba bababbb babbaaa babbaab babbaba babbabb babbbaa babbbab babbbba bbaaaba bbaabaa bbaabab bbaabba bbabaaa bbabaab bbababa bbababb bbabbaa bbabbab bbabbba bbbaaba bbbabaa bbbabab bbbabba bbbbaba

The 1st rejects include
a b aa ab bb aaa aab aba abb baa bab bba bbb aaaa aaab aabb abaa abab abbb baaa baab babb bbaa bbab bbbb aaaaa aaaab aaaba aaabb aabaa aabab aabba aabbb abaaa abaab ababb abbaa abbab abbba abbbb baaaa baaab baabb babbb bbaaa bbaab bbabb bbbaa bbbab bbbba bbbbb aaaaaa aaaaab aaaabb aaabaa aaabab aaabbb aabaaa aabaab aababb aabbaa aabbab aabbbb abaaaa abaaab abaabb ababaa ababab ababbb abbaaa abbaab abbabb abbbaa abbbab abbbbb baaaaa baaaab baaabb baabaa baabab baabbb babaaa babaab bababb babbaa babbab babbbb bbaaaa bbaaab bbaabb bbabaa bbabab bbabbb bbbaaa bbbaab bbbabb bbbbaa bbbbab bbbbbb aaaaaaa aaaaaab aaaaaba aaaaabb aaaabaa aaaabab aaaabba aaaabbb aaabaaa aaabaab aaababb aaabbaa aaabbab aaabbba aaabbbb aabaaaa aabaaab aabaabb aababbb aabbaaa aabbaab aabbabb aabbbaa aabbbab aabbbba aabbbbb abaaaaa abaaaab abaaabb abaabbb ababbbb abbaaaa abbaaab abbaabb abbabbb abbbaaa abbbaab abbbabb abbbbaa abbbbab abbbbba abbbbbb baaaaaa baaaaab baaaabb baaabbb baabbbb babbbbb bbaaaaa bbaaaab bbaaabb bbaabbb bbabbbb bbbaaaa bbbaaab bbbaabb bbbabbb bbbbaaa bbbbaab bbbbabb bbbbbaa bbbbbab bbbbbba bbbbbbb

As I understand it nothing is more powerful that the turning machine as language acceptors, and I wrote this algorithm on a computer, so there has to be a TM for this question.

Don't try to model the parts with regular expressions, if you need a TM for this there is no way a FA will work...

I will try this tomorrow
Re: Oct 2006 Exam Question 5.
November 03, 2009 10:51AM
Has anyone come up with a solution to this problem? example TM yet, any takers?
avatar Re: Oct 2006 Exam Question 5.
November 03, 2009 12:04PM
I think i've got it now: http://tinypic.com/view.php?pic=35bz2o2&s=4

String at
1: (a+b)evena (odd in total)
2: (a+b)evenb (odd in total)
3: (a+b)even (even in total)
4: (a+b)evenba (even in total)
HALT if this is the end, otherwise repeat 1-4
5: (a+b)odd and end of string - >string is odd length
Now we start going the other direction looking for ab (ie. ba in reverse)
6: Get to the last b in a clump of b's
7: Get to the last a in a clump of a's
8: Get to the last b in a clump of b's (1st ab found)
9: Get to the last a in a clump of a's
10: A b has been found. (2nd ab found)
Then go back to 9 but move TAPE to the right which leads to an infinite loop.

(even odd implies * but with an even/odd amount of letters)

--
"A man is the less likely to become great the more he is dominated by reason: few can achieve greatness - and none in art - if they are not dominated by illusion." Mr. Doctor
avatar Re: Oct 2006 Exam Question 5.
November 03, 2009 12:15PM
Do you really think the answer is sooo difficult? It was an exam question where you don't have hours to puzzle out something? Will have a go at it myself in a while & will report back.
avatar Re: Oct 2006 Exam Question 5.
November 03, 2009 12:18PM
Wait. I forgot to check during the reverse part that the word is of odd length... that means it's even longer...

Never mind that. The oddness is checked before entering the top section.

I don't think it's that difficult, it's rather a matter of looking at the question in a different way. The default response would be to try and test everything at the same time and the same direction. When I realised that wouldn't work I looked for a way to do the two test separately. So first test to see if the word gets accepted. If the word crashes in the bottom half of the TM it's even and doesn't end with ba. Otherwise the word must be odd. So then you search for 2 ba's. If find it just go back and forth. Otherwise the machine will go over position i and crash (odd without 2 ba's).

--
"A man is the less likely to become great the more he is dominated by reason: few can achieve greatness - and none in art - if they are not dominated by illusion." Mr. Doctor
Re: Oct 2006 Exam Question 5.
November 03, 2009 01:13PM
If we get a question like this, there is no hope for me 'cause only got 16 minutes to figure out and draw it
Anonymous User
Re: Oct 2006 Exam Question 5.
November 03, 2009 04:30PM
I believe this is the solution (in table format as per pg546)

As @malberts said, 1st establish even/odd and then do the specifics...

 0  1 a A R
 0  1 b B R
 1  2 a a R
 1  2 b b R
 1  8 ^ ^ L
 2  1 a a R
 2  1 b b R
 2  3 ^ ^ L
 3  4 a a L
 4  5 b b R
 4  5 B b R
 5  6 a a R
 6  7 ^ ^ R
 7 HALT-STATE
 8  8 a a L
 8  8 b b L
 8  9 A a R
 8 10 B b R
 9  9 a a R
 9 10 b b R
10 11 a a R
10 10 b b R
11 11 a a R
11 12 b b R
12 13 a a R
12 12 b b R
13 13 a a R
13 13 b b R
13 13 ^ ^ R
Sorry, only registered users may post in this forum.

Click here to login