0

I tried to do this type of some good random exercise, but I was completely working on it for a month and totally felt unbelievable. I need to see the solution for this type of exercise in order to understand :(. I have hint like 'IF, ELSE, DO' statements, but the solution could help me really to understand completely about Turing Machine.

Consider the alphabets {d, r} Write a Turing Machine
that will recognise the language Stretch(x+1). This is the language of all strings that
contain a continuous string of occurrences of the two letters, followed by ‘*’,
followed by another string of letters with x+1 occurrences of the each letter where
there was a single occurrence in the first string of letters. Here, x = 1. Input to the machine is non-null strings of a, b, *. As an
example, where the letters are ‘a’ and ‘b’ (and x=1) aba*aabbaa, bb*bbbb and
baab*bbaaaabb are in the language, but abb*abbb is not. You may assume that you
have subroutines for writing 0 in the first cell and deleting the rest of the tape and for writing 1 in the first cell and deleting the rest of the tape.

For the mercy, I wish you could help me.


Thank you so much.

Regards


Sabrina

4
Contributors
12
Replies
13
Views
6 Years
Discussion Span
Last Post by paoconnell
0

If you can build an algorithm for this problem, it means that the problem is computable, therefore it can be done using a Turing machine (Church–Turing thesis). When you look at a string what do you do to determine if it's in the language? Perhaps something of the sort of:

  1. Check the first letter
  2. Go to the * character, and check if the two letters afterwards consists with the first character you have checked
  3. Repeat the steps for all the characters, checking the character before the * and then jumping to the appropriate location after the * (this can be done easily holding some sort of index)
  4. If one of the characters was inconsistent with the language, return false.
  5. if there was no *, return false.
  6. If all letters were consistent and you have reached the end of the string, return true.

An algorithm exists to solve the problem, therefore you can have a Turing machine that will accomplish it.

0

But I can't visualize in my head to be honest with you :(. I wish you could show me the solution for it and I really want to visualize my head, in the future I will be able to solve others by myself. Please dear, I'm begging that I want to learn more about Turing Machine. Once again, I hope you able to provide the solution above :(.

Best Regards

Sabrina

0

I gave you the solution - I have showed you an algorithm that solves the problem, therefore invoking the Church Turing thesis it can be done using a Turing machine.

0

But my dear, I cannot see any codes for turing machine above, when it says write a turing machine, does it mean write in code or as what you've written? I apology for being misunderstanding. Sorry

0

And one thing dear, as you have provided the solution, what is the code for of that solution?

0

How do you mean? dear if you don't mind explaining to me. Thank you so much for your help.

-1

Wiki is just peaky. I just want the full algorithms for the question above. I wish I could see and learn it in depth.

Votes + Comments
How about you do your own homework, or at least make a bit of effort, dear
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.