Turing Machine para verificar si la string dada es Even Palindrome o no

Una string w se llama palíndromo si leer w de izquierda a derecha da el mismo resultado que leer w de derecha a izquierda. Un palíndromo par tiene un número par de símbolos.

Ejemplos:

Input : abaaba 
Output :YES

Input :abba
Output :YES

Input :abbaba
Output :NO

Input :Empty String or  
Output :YES 

Representación básica:

Inicio del cálculo:
la cinta contiene la string de entrada w, el cabezal de la cinta está en el símbolo más a la izquierda de w y la máquina de Turing está en el estado de inicio Q0.

Idea básica:
el cabezal de la cinta lee el símbolo más a la izquierda de w, borra este símbolo y lo «recuerda» por medio de un estado. Luego, el cabezal de la cinta se mueve al símbolo más a la derecha y comprueba si es igual al símbolo (ya eliminado) más a la izquierda.

Si son iguales, se elimina el símbolo más a la derecha, el cabezal de la cinta se mueve al nuevo símbolo más a la izquierda y se repite todo el proceso. De lo contrario, la máquina no puede alcanzar el estado final y la string será rechazada.

Significados de los símbolos utilizados:
R, L: dirección de movimiento de una unidad a cada lado.
B-Blank
a, b-símbolos cuya string de combinación se va a probar

Procedimiento de trabajo :

• Paso 1:
  comenzamos con el estado Q0 si obtenemos un símbolo «a» como entrada, entonces también debería haber «a» al final de la string, entonces solo la string es palíndromo y tenemos que verificar eso. Primero hacemos que la entrada actual «a» a B quede en blanco y vamos al estado Q1 hacia la derecha para atravesar la string hasta llegar al final. Mantenga los símbolos de entrada a o b cualquiera que sea el modo en que debe permanecer sin cambios.

  Podemos llegar al final de la string cuando obtenemos Blank como el símbolo de entrada, luego cambiamos el estado a Q2 y probamos si el símbolo anterior es «a», luego cambiamos al estado Q3 y luego solo lo reemplazaremos por Blank y tenemos Probamos con éxito que la string es palíndromo hasta este punto, ahora vamos a viajar hacia atrás o hacia la izquierda (manteniendo a y b sin cambios, lo que viene en el camino) en la string y hasta que obtengamos Blank, que es el símbolo que hicimos Blank al principio y cambiamos de estado a Q0. Ahora repetimos el mismo procedimiento para «b» como entrada.

• Paso 2:
  hasta este punto, si la string fuera palíndromo, habría regresado al estado Q0 después de todas las iteraciones y si la string no fuera palíndromo, nos atascaríamos en los estados Q2 o Q5 y ​​cuando nos atascáramos en estos puntos no podemos llegar a Q0 y por lo tanto no puede alcanzar el estado final o el estado de aceptación Q7.
• Paso 3:
  si la string era palíndromo, solo quedará el símbolo en blanco y, por lo tanto, lo probamos en Q0 si nos quedamos en blanco, por lo tanto, la string se acepta y es palíndromo, en este punto se incluye una condición más que es de string nula o como string vacía también es palíndromo, por lo tanto, se acepta.