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

Prerrequisito – Máquina de Turing

En lenguaje dado L = {a ⁱ b ^j c ^k | i>j>k; k ≥ 1}, cada string de ‘a’, ‘b’ y ‘c’ tiene cierto número de a, luego cierto número de b y luego cierto número de c. La condición es que el conteo de los 3er símbolos debe ser al menos 1. ‘a’ y ‘b’ pueden tener tantos, pero el conteo de c es menor que el conteo de ‘b’ y el conteo de ‘b’ es menor que el conteo de ‘ a’. Suponga que la string termina con ‘$’. 
Ejemplos: 
 

Input: a a a b b c  
       Here a = 3, b = 2, c = 1
Output: ACCEPTED
          
Input: a a b b c c c
       Here a = 2, b = 2, c = 3 but |a|>|b|>|c|
Output: NOT ACCEPTED 

Representación de cinta: 

Acercarse: 
 

1. Comparar dos elementos haciendo A y D como un solo elemento.
2. Después de eso Comparando A & D.
3. Si |C| es mayor que |(A, D)|, entonces no se acepta.
4. Si |D| es mayor que |A|, entonces no se acepta.
5. De lo contrario, se acepta.

Pasos: 
 

• Paso 1: Convierta A en X y muévase a la derecha y vaya al paso 2. 
   
• Paso 2: sigue ignorando A e Y y muévete hacia la derecha. Convierta D en Y y muévase a la derecha y vaya al paso 3.
• Paso 3: siga ignorando D y Z y muévase hacia la derecha. Si se encuentra C, conviértalo en Z y muévase hacia la izquierda hasta el paso 4. Si se encuentra B, ignórelo, muévase hacia la izquierda y vaya al paso 5.
• Paso 4: siga ignorando Z, A, Y y D y muévase hacia la izquierda. Si encuentra X, ignórelo, muévase a la derecha y vaya al paso 1.
• Paso 5: Sigue ignorando D, Y y A y muévete hacia la izquierda. Ignore X, mueva a la derecha y vaya al paso 6.
• Paso 6: Convierta A en X y muévase a la derecha y vaya al paso 7.
• Paso 7: siga ignorando Y y A y muévase hacia la derecha. Si encuentra B, ignórelo y muévase a la izquierda y vaya al paso 8. Si D, haga que sea Y, muévase a la derecha y vaya al paso 5.
• Paso 8: detener la máquina (se acepta la string)

Diagrama de transición de estado: 

Aquí, Q0 muestra el estado inicial y Q1, Q2, Q3, Q4, Q5, Q6 muestra el estado de transición y Q7 muestra el estado final. A, C, D son las variables utilizadas y R, L muestra derecha e izquierda. 

Explicación: 
 

• Usando Q0, cuando se encuentre A, conviértalo en X y vaya a la derecha y al estado Q1.
• En el estado Q1, ignore todo A e Y y vaya a la derecha. Si D encontró, conviértalo en Y y vaya a la derecha al siguiente estado Q2.
• En Q2, ignora todo D, Z y muévete a la derecha. Si B encuentra, ignóralo, muévete a la izquierda y ve al estado Q4, si C encuentra, haz que Z muévase a la izquierda y a Q3.
• En el estado Q3, ignore todo Z, D, Y, A y muévase hacia la izquierda. Si encuentra X, ignórelo, muévase hacia la derecha hasta Q0.
• En Q4, ignore todo A, Y, D y muévase a la izquierda. Si encuentra X, ignórelo, muévase a la derecha hasta el estado Q6.
• En el estado Q6, si A encuentra, haga que X se mueva a la derecha al estado Q5
• En Q5, ignore todo A, Y y muévase a la derecha. Si encuentra D, conviértalo en Y y muévase a la derecha hasta el estado Q4. Si encuentra B, ignórelo y muévase a la izquierda hasta Q7.
• Si se alcanza el estado Q7, se producirá el resultado de la aceptación de la string.

Nota: Para la comparación de |A|, |D|, |C|, se utiliza el concepto de Máquina de Turing como Comparador .