Question

Introduce a Turing machine to decide the languages to follow. You must
Algorithmic description, but with a sufficient level of detail.
You can use the variants of the original model of the Turing machine.

{w w^R w | where w is a word formed by 0's and 1's}

{w ∈ {a, b}∗| w is a palindrome and has the same number of a's and b's}.

Please describe which variant of Turing whether it is with a tape or multi tape.

whether the machine is deterministic or not deterministic

Answer 1

Answer

Turing Machine for- {w w^R w | where w is a word formed by 0's and 1's}

We are using here Single Tape Turing Machine.

The machine is non-deterministic Turing machine.

let us consider the tape alphabet {0, 1, a, b, c, d} and make a single-tape TM that recognizes w w^R w.

the TM works as following steps-:

1. Replace 0's & 1's in the prefix w w^R  with a's and b's.
2. Check whether w w^R is a palindrome.
3. Restore the tape to its original state.
4. Replace 0's & 1's in the suffix w^R w   with c's and d's.
5. See whether w^R is a palindrome.

note that ww^Rw must have length 3n for some n.

this is simply one easy way to show that there exists a TM to recognize w w^R w . So with details, showing that there exists an algorithm.

Step 1-

• Pre-condition: The tape starts with a blank, contains any string in (0+1)*, and is followed by an infinite string of blank squares.

• Post-condition: Halts if tape is empty or if length is not a multiple of 3; else, the tape begins with a blank, is followed by (a+b)²ⁿ (c+d)ⁿ, followed by an infinite string of blanks.

  1. Move to the right.
  2. If empty, halt accept. Otherwise, Scan to the right until you find an empty tape square, then move left.
  3. Change the tape to c if 0 or d if 1.
  4. Scan left until you find an empty tape square. Move right.
  5. If the tape is 0 or 1, change to a or b then move right. If the tape is c or d, halt reject.
  6. If the tape is 0 or 1, change to a or b then move right. If the tape is c or d, halt reject.
  7. If tape is c or d, scan to the beginning of the tape and go to Step 2. Otherwise, scan right until c or d, then move left.
  8. Change the tape to c if 0 or d if 1.
  9. Scan left until you find either a or b. Move right.
  10. Repeat starting at 4.

Step 2 -

• Pre-condition: The tape begins with a blank, is followed by (a+b)^2n (c+d)^n, followed by an infinite string of blanks.

• Post-condition: Halts if the prefix (a+b)²ⁿ isn't a palindrome; otherwise, leaves the tape in a state like D (c+d)^3n D*

  1. Move right.
  2. If tape is a (or b), move right. If tape is c or d, go to the beginning of the tape, then go to Step 3.
  3. If the tape is c, d or blank, halt reject. Otherwise, scan right until you find a c, d or blank. Move left.
  4. If the tape is a b (or a), halt reject. Otherwise, change this to a c (or d) and scan back to the left until you see a blank, a c or a d. Move right. Change a (or b) to c (or d). Move right.
  5. Repeat starting at step 2.

Step 3-

• Pre-condition: Tape is D (c+d)^3n D*

• Pos-tcondition: Tape is D (0+1)^3n D*

  1. Move right.
  2. If tape is c, write 0 and move right. If tape is d, write 1 and move right. If tape is blank, move to first blank space at the end of tape and go to step 4.
  3. Repeat step 2.

Step 4 and 5 work just like steps 1 and 2, except you work backwards (the tape now looks like D (c+d)^n (a+b)^2n D*, and you must check to see whether the (a+b)^2n part is a palindrome.

Any string passing both these tests must be of the form w w^R w where w is in (0+1)*.