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 i 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. 
     

Publicación traducida automáticamente

Artículo escrito por RishabhMalik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *