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

Prerrequisito – Máquina de Turing 
El lenguaje L = {ww | w ∈ {0, 1}} dice que cada string de 0 y 1 que va seguida de sí misma cae dentro de este lenguaje. La lógica para resolver este problema se puede dividir en 2 partes: 
 

1. Hallar el punto medio de la cuerda 
    
2. Después de haber encontrado el punto medio hacemos coincidir los símbolos 
    

Ejemplo: entendámoslo con la ayuda de un ejemplo. Vamos a la string 1 0 1 1 0 1, entonces w = 1 0 1 y la string tiene la forma (ww). 
Lo primero que hacemos es encontrar el punto medio. Para esto, convertimos 1 al principio en Y y lo movemos a la derecha hasta el final de la string. Aquí convertimos 1 en y. 

Ahora nuestra string se vería como Y 0 1 1 0 Y. Ahora muévase hacia la izquierda hasta encontrar una X o Y. Cuando lo hagamos, convierta el 0 o 1 a la derecha en X o Y respectivamente y luego haga lo mismo a la derecha final. Ahora nuestra string se vería como YX 1 1 XY. Luego, convierta estos 1 también y finalmente se vería como YXY Y X Y. 

En este punto, has logrado el primer objetivo que era encontrar el punto medio. Ahora convierta todo X e Y a la izquierda del punto medio en 0 y 1 respectivamente, de modo que la string se convierta en 1 0 1 YX Y. Ahora, convierta el 1 en Y y muévase a la derecha hasta encontrar Y al principio de la parte derecha de la string. y convierta esta Y en un espacio en blanco (indicado por B). Ahora la string se parece a Y 0 1 BX Y. 

De manera similar, aplique esto en 0 y x seguido de 1 e Y. Después de que esta string se vea como YXYBB B. Ahora que no tiene 0 ni 1 y todas las X e Y en la parte derecha de la string se convierten en espacios en blanco, por lo que nuestra string ser aceptado. 

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

Enfoque utilizado: 
lo primero es encontrar el punto medio de la string, convertir un 0 o 1 desde el comienzo de la string en X o Y respectivamente y un 0 o 1 correspondiente en X o Y desde el final de la string. Después de hacerlo continuamente, se llega a un punto en el que todos los 0 y 1 se han convertido en X e Y respectivamente. En este punto, estás en el punto medio de la cuerda. Así, nuestro primer objetivo está cumplido. 

Ahora, convierta todas las X e Y a la izquierda del punto medio en 0 y 1. En este punto, la primera mitad de la string tiene la forma de 0 y 1. La segunda mitad de la string tiene la forma de X e Y. 

Ahora, comience desde el principio de la string. Si tiene un 0, conviértalo en X y muévase hacia la derecha hasta llegar a la segunda mitad, aquí si encontramos X, luego conviértalo en un espacio en blanco (B). Luego retroceda hasta encontrar una X o una Y. Convertimos el 0 o el 1 a la derecha en X o Y respectivamente y, correspondientemente, convertimos su X o Y en la segunda mitad de la string en un espacio en blanco (B). 

Siga haciendo esto hasta convertir todos los símbolos de la parte izquierda de la string en X e Y y todos los símbolos de la derecha de la string en espacios en blanco. Si una parte se convierte por completo pero aún quedan algunos símbolos en la otra mitad sin cambios, entonces la string no se aceptará. Si no encontró una X o Y en la segunda mitad para un 0 o 1 correspondiente respectivamente en la primera mitad. Entonces tampoco se aceptará la string. 

Ejemplos: 
 

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

Input  : 1 0 1 1 1 0 1
Output : Not accepted

• Paso 1: 
  Si el símbolo es 0, reemplácelo por X y muévase a la derecha 
  Si el símbolo es 1, reemplácelo por Y y muévase a la derecha, 
  Vaya al estado Q1 y paso 2 
  —————————————— — 
  Si el símbolo es X reemplácelo por X y muévase a la izquierda o 
  Si el símbolo es Y reemplácelo por Y y muévase a la izquierda, 
  Vaya al estado Q4 y al paso 5 

   

• 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évase a la izquierda o 
  Si el símbolo es Y reemplácelo por Y y muévase a la izquierda o 
  Si el símbolo es $reemplácelo por $y muévase a la izquierda, Vaya al estado Q2 y paso 3 

   

• Paso 3: 
  si el símbolo es 0, reemplácelo por X y muévase a la izquierda, o 
  si el símbolo es 1, reemplácelo por Y y muévase a la izquierda, 
  vaya al estado Q3 y al paso 4 

   

• Paso 4: 
  Si el símbolo es 0, reemplácelo por 0 y muévase hacia la izquierda, permanezca en el mismo estado 
  Si el símbolo es 1, reemplácelo por 1 y muévase hacia la izquierda, permanezca en el mismo estado 
  —————————— ————— 
  Si el símbolo es X reemplácelo por X y muévase a la derecha o 
  Si el símbolo es Y reemplácelo por Y y muévase a la derecha, 
  Vaya al estado Q0 y paso 1 

   

• Paso 5: 
  Si el símbolo es X, reemplácelo por X y muévase hacia la izquierda o 
  Si el símbolo es Y, reemplácelo por Y y muévase hacia la izquierda 
  Vaya al estado Q4 y al paso 6 

   

• Paso 6: 
  Si el símbolo es X, reemplácelo por 0 y muévase hacia la izquierda, permanezca en el mismo estado 
  Si el símbolo es Y, reemplácelo por 1 y muévase hacia la izquierda, permanezca en el mismo estado 
  – – – – – – – – – – – – – – – – – – – — 
  Si el símbolo es $, reemplácelo por $y muévase a la derecha 
  Vaya al estado P4 y al paso 7 

   

• Paso 7: 
  Si el símbolo es 0, reemplácelo por X y muévase a la derecha, vaya al estado Q6 y paso 8 
  Si el símbolo es 1, reemplácelo por Y y muévase a la derecha, vaya al estado Q7 y muévase a la derecha, vaya al estado Q7 y paso 9 
  – – – – – – – – – — – – – – – – – – – – — 
  Si el símbolo es B, reemplácelo por B y muévase hacia la izquierda, CADENA ACEPTADA, VAYA AL ESTADO FINAL P9 

   

• Paso 8: 
  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 B, reemplácelo por B y muévase a la derecha, permanezca en mismo estado 
  – — – – – – – – – – – – – – – – – – – – – – 
  Si el símbolo es X, reemplácelo por B y muévase hacia la izquierda 
  Vaya al estado Q8 y al paso 10 

   

• Paso-9: 
   

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 B, reemplácelo por B y muévase a la derecha, permanezca en el mismo estado 
– — – – – – – – – – – – – – – – – – – – – – 
Si el símbolo es Y, reemplácelo por B y muévase hacia la izquierda 
Vaya al estado P8 y al paso 10 

• Paso 10: 
  Si el símbolo es 0, reemplácelo por 0 y muévase a la izquierda, permanezca en el mismo estado 
  Si el símbolo es 1, reemplácelo por 1 y muévase a la izquierda, permanezca en el mismo estado 
  Si el símbolo es B, reemplácelo por B y muévase a la izquierda, permanezca en mismo estado 
  – — – – – – – – – – – – – – – – – – – – – – 
  Si el símbolo es Y reemplácelo por Y y muévalo a la derecha o 
  Si el símbolo es X reemplácelo por X y muévalo a la derecha 
  Vaya al estado Q5 y paso 7