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