Construya una máquina de Turing para L = {aibjck | i*j = k; yo, j, k ≥ 1}

Prerrequisito – Máquina de Turing 
En un idioma dado, L = {a ⁱ b ^j c ^k | i*j = k; i, j, k ≥ 1}, donde cada string de ‘a’, ‘b’ y ‘c’ tiene un cierto número de a, luego un cierto número de b y luego un cierto número de c. La condición es que cada uno de estos 3 símbolos aparezca al menos una vez. ‘a’ y ‘b’ pueden aparecer muchas veces, pero las apariciones de ‘c’ deben ser iguales al producto de las apariciones de ‘a’ y las apariciones de ‘b’. Suponga que la string termina con ‘$’. 

Ejemplos – 
 

Input: a a b b b c c c c c c  
       Here a = 2, b = 3, c = 2 * 3 = 6  
Output: ACCEPTED
          
Input: a a b b c c c
       Here a = 2, b = 2, c = 3 but c should be 4 
Output: NOT ACCEPTED 

Enfoque utilizado: escanee la entrada desde la izquierda. 
 

1. Primero, reemplaza una ‘a’ con ‘X’ y muévete 1 paso a la derecha. Luego omite todas las a y muévete a la derecha. 
2. Cuando el puntero llega a la primera parada ‘b’. Reemplace una ‘b’ con ‘Y’, luego muévase a la derecha saltándose todas las b intermedias y correspondientes a la ‘b’ reemplazada, ahora reemplace una ‘c’ con ‘Z’ y muévase a la izquierda. 
3. Ahora muévase hacia la izquierda saltándose todas las ‘Z’ y ‘b’ en el camino. 
4. Cuando el puntero alcance la ‘Y’ más reciente, muévase hacia la derecha. 
5. Si el puntero apunta a ‘b’, repita los pasos 2 a 4; de lo contrario, si el puntero apunta a ‘Z’, muévase hacia la izquierda mientras reemplaza todas las ‘Y’ por ‘b’ y omite todas las a. 
6. Cuando el puntero llegue a la ‘X’ más reciente, muévase un paso a la derecha. 
7. Si el puntero sigue apuntando a ‘a’, repita todos los pasos anteriores; de lo contrario, si el puntero está en ‘b’, muévase hacia la derecha omitiendo todas las ‘b’ y ‘Z’. 
8. Cuando se alcance $, muévase a la izquierda. La string es ACEPTA.