Welcome! Log In Create A New Profile

Advanced

Turing Machine Questions

Posted by RiaanR 
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
Forums Messages New
avatar
RiaanR
Turing Machine Questions
June 06, 2007 01:01PM
I have some general Turing Machine questions:

1. If the tape head moves to the left of cell i, and crashes, would it be any different, than a "normal" crash if the word is not accepted?

2. I see on some examples on the web there is a N symbol, where L is for left, R is for Right and N is to do nothing, Are we allowed to use the N?
Reply Quote
iva
Re: Turing Machine Questions
June 06, 2007 01:10PM
N is the same as the S(tay) option, which they don't really want us to use ( Rather show that you nkow how to loop back and forth between characters), Stay option is somewhere i nthink in the last chapter?

Yes a crash is a crash, if you say have a loop between 2 states and one is state 1 ( Starting state) and the word gets stuck at that point and crashes, its crashed.. wherever whenever the word can't move
( sorry , this is rushed , maybe smoeone can put this more eloquently : )
hope it helped though, just whatever you do don't use N/S
Reply Quote
avatar
RiaanR
Re: Turing Machine Questions
June 07, 2007 07:42AM
Thanks,
Are we allowed then to use the INSERT and DELETE sub's without showing how they work?
Reply Quote
iva
Re: Turing Machine Questions
June 07, 2007 07:58AM
nope, the first line of the assignment states:

DO not use subroutines INSERT and DELETE

besides i can't remember needing them at all for this assignment smiling smiley
Reply Quote
avatar
RiaanR
Re: Turing Machine Questions
June 07, 2007 08:40AM
Oh I see that now, I must have misread it. sad smiley
Reply Quote
iva
Re: Turing Machine Questions
June 07, 2007 09:06AM
don't worry about inserts and deletes we don't ned them for anything in this assignment
Reply Quote
Annie
Re: Turing Machine Questions
June 07, 2007 11:54AM
Hi all, i'm really struggling with Qst 4 of Ass 3.

I'm assuming the TM should accept words in the format ab, aabb, aaabbb, ect. based on point 1. I drew a machine that accepts this perfectly.

Point 2, the loop, i drew another machine that loops on all even length words that end on ba.

So, now i have two seperate machines, works great, but do not know how to combine them into one machine.

Am i approaching this incorrectly? Is there a better way to understand TMs - a website maybe that teaches you a bit more?

Thanks guys!
Reply Quote
iva
Re: Turing Machine Questions
June 07, 2007 12:09PM
HI Annie, i approached this machine same as you getting them both right first. then to combine them first start with the even-word-ending-in-ba TM, and at the point where the 'b' or 'a' at the end does not exist move on to check if the word is a^nb^n

IE so where you got the state to check the last letter to be 'a' as well as the state of the 2nd last letter checking for a 'b' there you can create 2 arrows coverging to a new state which is going to be the start of where your a^nb^n machine is and you carry on from there..

does this make sense?
Reply Quote
Annie
Re: Turing Machine Questions
June 07, 2007 12:38PM
Excellent! Thanks iva, i'm glad to know that's how you did it as well (makes me feel somewhat less confused smile

I think i tried to combine the 1st machine to the 2nd at the wrong state perhaps and maybe that's why it didn't work, so i'm going to try what u suggested as it makes more sense now.

Again, thanks for the help smiling smiley
Reply Quote
iva
Re: Turing Machine Questions
June 07, 2007 12:58PM
anytime spinning smiley sticking its tongue out
Reply Quote
avatar
RiaanR
Re: Turing Machine Questions
June 08, 2007 11:21AM
is a and b, part of ODDPALINDROME if the alphabet is {a, b} ?
Reply Quote
iva
Re: Turing Machine Questions
June 08, 2007 11:28AM
yep , only a and b ( and you can use replacement characters like # or spaces or *)
Reply Quote
avatar
RiaanR
Re: Turing Machine Questions
June 08, 2007 11:31AM
Thanks. smile
Reply Quote
iva
Re: Turing Machine Questions
June 08, 2007 11:42AM
pleasure, have you had a look in the book there is an example somewhere ( i think the first chapter we had to read for this assignment) that has a PALINDROME TM, which accepts odd as well as even palindromes, i'm thinking maybe you haven't seen this because it gives you almost the whole answer for this, although for the assignment we are only meant to do a TM accepting ODDPALIMDROME only and it must crash for even, but you can use the example as a basis
Reply Quote
Newer Topic Older Topic
Sorry, only registered users may post in this forum.

Click here to login