Construya una máquina de Turing para el lenguaje L = {wwr | w ∈ {0, 1}}

Prerrequisito – Máquina de Turing
El idioma L = {ww ^r | victoria; {0, 1}} representa un tipo de idioma en el que usa solo 2 caracteres, es decir, 0 y 1. La primera parte del idioma puede ser cualquier string de 0 y 1. La segunda parte es el reverso de la primera parte. Combinando ambas partes se formará una string. Cualquier string que caiga en esta categoría será aceptada por este idioma. El principio y el final de la string están marcados con el signo $.

Por ejemplo, si la primera parte w = 1 1 0 0 1, entonces la segunda parte w ^r = 1 0 0 1 1. Es claramente visible que w ^r es el reverso de w, por lo que la string 1 1 0 0 1 1 0 0 1 1 es una parte del lenguaje dado.

Ejemplos –

Input : 0 0 1 1 1 1 0 0
Output : Accepted
Input : 1 0 1 0 0 1 0 1 
Output : Accepted

Representación básica –

Suposición: Reemplazaremos 0 por Y y 1 por X.

Enfoque utilizado:
primero verifique el primer símbolo, si es 0, luego reemplácelo por Y y por X si es 1. Luego vaya al final de la string. Así que el último símbolo es el mismo que el primero. Lo reemplazamos también por X o Y dependiendo de ello.
Ahora regrese nuevamente a la posición al lado del símbolo, reemplace desde el principio y repita el mismo proceso que se indicó anteriormente.

Una cosa importante a tener en cuenta es que, dado que w ^r es el reverso de w, ambos tendrán el mismo número de símbolos. Cada vez que reemplace un símbolo n desde el principio de la string, reemplace el símbolo n correspondiente desde el final.

• Paso 1:
  si el símbolo es 0, reemplácelo por Y y muévase a la derecha, vaya al estado Q2
  Si el símbolo es 1, reemplácelo por X y muévase a la derecha, vaya al estado Q1
• Paso 2:
  Si el símbolo es 0, reemplácelo por 0 y muévase a la derecha, permanezca en el mismo estado
  Si el símbolo es 1, reemplácelo por 1 y muévase a la derecha, permanezca en el mismo estado
  —————————————— ————————-
  Si el símbolo es X, reemplácelo por X y muévalo a la derecha, vaya al estado Q3
  Si el símbolo es Y, reemplácelo por Y y muévase a la derecha, vaya al estado Q3
  Si el símbolo es $, reemplácelo por $y mover a la derecha, ir al estado Q3
• Paso 3:
  si el símbolo es 1, reemplácelo por X y muévase a la izquierda, vaya al estado Q4
  Si el símbolo es 0, reemplácelo por Y y muévase a la izquierda, vaya al estado Q5
• Paso 4:
  Si el símbolo es 1, reemplácelo por 1 y muévase hacia la izquierda.
  Si el símbolo es 0, reemplácelo por 0 y muévase hacia la izquierda.
  Permanezca en el mismo estado .
• Paso 5:
  Si el símbolo es X, reemplácelo por X y muévase a la derecha
  . Si el símbolo es Y, reemplácelo por Y y muévase a la derecha.
  Vaya al estado Q0.
• Paso 6:
  Si el símbolo es X, reemplácelo por X y muévalo a la derecha
  Si el símbolo es Y, reemplácelo por Y y muévalo a la derecha
  Vaya al estado Q6
  ELSE
  Vaya al paso 1
• Paso 7:
  Si el símbolo es X, reemplácelo por X y muévase a la derecha, permanezca en el mismo estado
  Si el símbolo es Y, reemplácelo por Y y muévase a la derecha, permanezca en el mismo estado
  Si el símbolo es $, reemplácelo por $y muévase a la izquierda, LA CADENA ES ACEPTADO, IR AL ESTADO FINAL P7