Give implementationlevel descriptions of Turing machines tha

Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet = {a, b}.

(a) {w | w contains twice as many a\'s as b\'s}

(b) {w | w does not contain twice as many a\'s as b\'s}

Solution

(a) {w | w contains twice as many a\'s as b\'s} :

1. Scan the tape and mark the first \'b\' which has not been marked. If nounmarked \'b\' is
     found go to stage 5. Otherwise move the head back to the start of the tape.

2. Scan the tape until an unmarked a is found, mark the a, if no a’s are found reject

3. Scan the tape once more until an unmarked zero is found, mark the a, if no a\'s arefound
     reject

4. Move the head back to the start of the tape and go to stage 1

5. Move the head back to the start of the tape. Scan the tape to see if any unmarked a’s are
     found. If none are found accept, otherwise reject.

(b) {w | w does not contain twice as many a\'s as b\'s}

1. Scan the tape and mark the first b which has not been marked. If no unmarked b’s are found go to stage 5. Otherwise move the head back to the start of the tape

2. Scan the tape until an unmarked a is found, mark the a, if no a ’s are found accept

3. Scan the tape once more until an unmarked zero is found, mark the a,if no a’s are found
accept

4. Move the head back to the start of the tape and go to stage 1

5. Move the head back to the start of the tape. Scan the tape to see if any unmarked a’s are
found. If none are found reject, otherwise accept.