Our goal is to construct a deterministic one-tape Turing machine that accepts strings over Σ = {a, b} which are palindromes. A palindrome is a string that is the same when read forwards and backwards, for example, abbabba. The Turing machine should operate in the following way: 1. Remember the first character of the input in the state control, and erase this character (replace it with a blank). 2. Move the head to the last (right-most) character of the input. 3. Verify that this character is the same character as the one stored in the state control. If it is, delete this character. If it is a different character, immediately halt and reject. 4. Move the head to the left-most character of the input. 5. If there are any characters left on the input, repeat from step 1. 6. If in step 1 or 3 the tape is empty (i.e. all characters of the input have been erased), halt and accept. First, take a minute to think about the algorithm and convince yourself that it indeed accepts all palindromes and no other string. (You do not need to submit anything for this step, but think about it!) Then draw a transition diagram for this Turing machine. The machine must follow the algorithm described above. Also, make sure that your machine handles all edge cases correctly; in particular, it should accept the empty string and any one-character string.
Our goal is to construct a deterministic one-tape Turing machine that accepts strings over Σ = {a, b} which are palindromes. A palindrome is a string that is the same when read forwards and backwards, for example, abbabba. The Turing machine should operate in the following way:
1. Remember the first character of the input in the state control, and erase this character (replace it with a blank).
2. Move the head to the last (right-most) character of the input.
3. Verify that this character is the same character as the one stored in the state control. If it is, delete this character. If it is a different character, immediately halt and reject.
4. Move the head to the left-most character of the input.
5. If there are any characters left on the input, repeat from step 1.
6. If in step 1 or 3 the tape is empty (i.e. all characters of the input have been erased), halt and accept.
First, take a minute to think about the
Then draw a transition diagram for this Turing machine. The machine must follow the algorithm described above. Also, make sure that your machine handles all edge cases correctly; in particular, it should accept the empty string and any one-character string.
Step by step
Solved in 3 steps with 1 images
