Máquina de Turing para el lenguaje { www | w ∈ {a, b} }

Prerrequisito: máquina de Turing
Diseñe una máquina de Turing para una cuerda que contenga exactamente 3 repeticiones de w consecutivas.

Enfoque utilizado:
Primero, encontraremos la posición de separación de la primera w de la segunda w.
Ahora, uniremos la primera y la segunda w. Si ambos coinciden, la segunda string w se convertirá en una string de $.

Luego, uniremos la primera y la tercera w. Si ambos coinciden, la tercera string w se convertirá en una string de $. Si la string alcanza el estado Halt H, entonces se acepta.

Ejemplo –

Input: ababab
Output: Accepted
Input: abbabbabb
Output: Accepted
Input: ^ (Empty string)
Output: Accepted
Input: aba
Output: Not accepted 

Paso 1:
si el símbolo es $, reemplácelo por $y muévase a la derecha.

Vaya al estado Q1 y al paso 2.

Paso 2:
si el símbolo es a, reemplácelo por A y muévase a la derecha, o

Si el símbolo es b, reemplácelo por B y muévase a la derecha.

Vaya al estado Q2 y al paso 3.

————————————————-

Si el símbolo es A, reemplácelo por A y muévase hacia la izquierda, o

Si el símbolo es B, reemplácelo por B y muévase hacia la izquierda.

Vaya al estado P6 y al paso 7.

————————————————-

Si el símbolo es $, reemplácelo por $y se acepta la string.

Ir al estado final H.

Paso 3:
si el símbolo es a, reemplácelo por a y muévase a la derecha, permanezca en el mismo estado, o

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 A, reemplácelo por A y muévase hacia la izquierda, o

Si el símbolo es B, reemplácelo por B y muévase hacia la izquierda, o

Si el símbolo es $, reemplácelo por $y muévase hacia la izquierda.

Vaya al estado P3 y al paso 4.

Paso 4:
si el símbolo es un reemplácelo por A y muévase hacia la izquierda, o

Si el símbolo es b, reemplácelo por B y muévase hacia la izquierda,

Ir al estado Q4 y al paso 5

Paso 5:
Si el símbolo es un reemplácelo por A y muévase hacia la izquierda, o

Si el símbolo es b, reemplácelo por B y muévase hacia la izquierda,

Vaya al estado P5 y al paso 6

Paso 6:
si el símbolo es a, reemplácelo por a y muévase hacia la izquierda, permanezca en el mismo estado, o

Si el símbolo es b, reemplácelo por b y muévase hacia la izquierda, permanezca en el mismo estado.

————————————————

Si el símbolo es A, reemplácelo por A y muévase a la derecha, o

Si el símbolo es B, reemplácelo por B y muévase a la derecha, o

Vaya al estado Q1 y al paso 2.

Paso 7:
si el símbolo es A, reemplácelo por a y muévase hacia la izquierda, permanezca en el mismo estado, o

Si el símbolo es B, reemplácelo por b y muévase a la izquierda, permanezca en el mismo estado

————————————————-

Si el símbolo es $, reemplácelo por $y muévase a la derecha.

Vaya al estado P7 y al paso 8.

Paso 8:
si el símbolo es a, reemplácelo por A y muévase a la derecha.

Vaya al estado P9 y al paso 10.

————————————————––

Si el símbolo es b, reemplácelo por B y muévase a la derecha.

Vaya al estado P8 y al paso 9.

————————————————––

Si el símbolo es $, reemplácelo por $y muévase hacia la izquierda.

Vaya al estado P11 y al paso 12.

Paso 9:
si el símbolo es a, reemplácelo por a y muévase a la derecha, permanezca en el mismo estado, o

Si el símbolo es b, reemplácelo por b y muévase a la derecha, permanezca en el mismo estado, o

Si el símbolo es $, reemplácelo por $y muévase a la derecha, permanezca en el mismo estado

————————————————––

Si el símbolo es B, reemplácelo por $y muévase hacia la izquierda.

Vaya al estado P10 y al paso 11.

Paso 10:
si el símbolo es a, reemplácelo por a y muévase a la derecha, permanezca en el mismo estado, o

Si el símbolo es b, reemplácelo por b y muévase a la derecha, permanezca en el mismo estado, o

Si el símbolo es $, reemplácelo por $y muévase a la derecha, permanezca en el mismo estado.

————————————————––

Si el símbolo es A, reemplácelo por $y muévase hacia la izquierda.

Vaya al estado P10 y al paso 11.

Paso 11:
si el símbolo es a, reemplácelo por a y muévase hacia la izquierda, permanezca en el mismo estado, o

Si el símbolo es b, reemplácelo por b y muévase hacia la izquierda, permanezca en el mismo estado, o

Si el símbolo es $, reemplácelo por $y muévase hacia la izquierda.

————————————————––

Si el símbolo es A, reemplácelo por A y muévase a la derecha, o

Si el símbolo es B, reemplácelo por B y muévase a la derecha.

Vaya al estado P7 y al paso 8.

Paso 12:
si el símbolo es A, reemplácelo por a y muévase hacia la izquierda, permanezca en el mismo estado, o

Si el símbolo es B, reemplácelo por b y muévase a la izquierda, permanezca en el mismo estado.

————————————————––

Si el símbolo es $, reemplácelo por $y muévase a la derecha.

Vaya al estado P12 y al paso 13.

Paso 13:
si el símbolo es a, reemplácelo por A y muévase a la derecha.

Vaya al estado P14 y al paso 15.

————————————————––

Si el símbolo es b, reemplácelo por B y muévase a la derecha.

Vaya al estado P13 y al paso 14.

————————————————––

Si el símbolo es $, reemplácelo por $y se acepta la string.

Ir al estado final H.

Paso 14:
si el símbolo es a, reemplácelo por a y muévase a la derecha, permanezca en el mismo estado, o

Si el símbolo es b, reemplácelo por b y muévase a la derecha, permanezca en el mismo estado, o

Si el símbolo es $, reemplácelo por $y muévase a la derecha, permanezca en el mismo estado.

————————————————––

Si el símbolo es B, reemplácelo por $y muévase hacia la izquierda.

Vaya al estado P15 y al paso 16.

Paso 15:
si el símbolo es a, reemplácelo por a y muévase a la derecha, permanezca en el mismo estado, o

Si el símbolo es b, reemplácelo por b y muévase a la derecha, permanezca en el mismo estado, o

Si el símbolo es $, reemplácelo por $y muévase a la derecha, permanezca en el mismo estado.

————————————————––

Si el símbolo es A, reemplácelo por $y muévase hacia la izquierda.

Vaya al estado P15 y al paso 16.

Paso 16:
si el símbolo es a, reemplácelo por a y muévase hacia la izquierda, permanezca en el mismo estado, o

Si el símbolo es b, reemplácelo por b y muévase hacia la izquierda, permanezca en el mismo estado, o

Si el símbolo es $, reemplácelo por $y muévase hacia la izquierda.

————————————————––

Si el símbolo es A, reemplácelo por A y muévase a la derecha, o

Si el símbolo es B, reemplácelo por B y muévase a la derecha.

Vaya al estado P12 y al paso 13.

significado de los simbolos-

R- move right

L- move left

a- character a

b- character b

A- character A

B- character B 

Ejemplo:
Tenemos que probar la máquina de Turing para una string «ababab».

-> $ababab$ 
-> $Ababab$ 
-> $AbabaB$ 
->$AbabAB$ 
-> $ABabAB$ 
-> $ABaBAB$ 
-> $ABABAB$ 
-> $AbABAB$ 
-> $abABAB$ 
-> $AbABAB$ 
-> $Ab$BAB$ 
-> $AB$BAB$ 
-> $AB$$AB$ 
-> $Ab$$AB$ 
-> $ab$$AB$ 
-> $Ab$$AB$ 
-> $Ab$$$B$ 
-> $AB$$$B$ 
-> $AB$$$$$ (Accepted)