Question

1) Write a TM program to sort a nonempty string of A's and B. Assume the tape head starts on the leftmost character. For example if the tape contains BAABABB to start with, then when the machine halts AAABBBB will be left on the tape. Machine will be in the halt state (H) when done with tape head on the first nonblank character. Please give me a code

Answer 1

Answer: Sorting refers to arrange the symbols of a given string in a given order. A Turing Machine program to sort a given string will work as per the steps given below:

1. Find the leftmost character
2. do
   1. Find a 'B' at the leftmost position in string
   2. Try to find an 'A' right on 'B'.
   3. If such 'A' is found, then replace it with 'B'.
3. while a character is available to read in string

Based on this, we can specify Turing Machine Program as follows:

For this, we assume that '$' represents the sentinel.

--------------------------------------------------

1. Find leftmost character
   1. If leftmost character is A or B, write A or B on tape accordingly and move left.
   2. If leftmost character is $, write $ on tape and move right.
2. Try to find a ‘B’ in leftmost position:
   1. If character read is ‘A’, write ‘A’ on tape and move right.
   2. If character read is ‘B’, write ‘B’ on tape and move right.
   3. If $ is found, write ‘$’ on tape, move left and stop.
3. Try to find an ‘A’ on right of ‘B’, replace ‘A’ with ‘B’, then move left:
   1. If character read is ‘A’, write ‘B’ on tape and move left.
   2. If character read is ‘B’, write ‘B’ on tape and move right.
   3. If character read in ‘$’, write ‘$’ on tape, move left and stop.
4. Replace ‘B’ with ‘A’ after replace ‘A’ with ‘B’:
   1. If character read is ‘B’, write ‘A’ on tape and move left.

---------------------------------------------------