Construya una máquina de Turing para L = {aibjck | yo < j < k o yo > j > k}

Prerrequisito – Máquina de Turing
El lenguaje L = {a ⁱ b ^j c ^k | i < j < k o i > j > k} es lo mismo que la unión de dos lenguas L1={a ⁱ b ^j c ^k | yo < j < k } y L2={a ^yo segundo ^j c ^k | i > j > k }
En este idioma, 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 o
• El conteo de los primeros símbolos debe ser al menos 1. ‘b’ y ‘c’ pueden tener tantos, pero el conteo de a es menor que el conteo de ‘b’ y el conteo de ‘b’ es menor que el conteo de ‘c’.
• 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 b b c c c
       Here a = 1, b = 2, c = 3 
Output: ACCEPTED

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

Representación de cinta:

Acercarse:

1. Comparar dos elementos haciendo dos elementos como un solo elemento.
2. Después de eso, los elementos que se tratan como un solo elemento se comparan nuevamente.
3. Si |Primero| es mayor que |(Segundo, Tercero)| y |Segundo| mayor que |Tercera|, entonces se acepta.
4. Si |Tercero| es mayor que |(Primero, Segundo)| y |Primero| mayor que |Segundo|, entonces se acepta.
5. De lo contrario no se acepta.

Pasos:

• Paso 1: Convierta A en X y muévase a la derecha y vaya al paso 2. Si encuentra Y, ignórelo y muévase a la derecha al paso 5.
• 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 8.
• 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 Y y muévete hacia la derecha. Ignore Z, muévase a la izquierda y vaya al paso 11. Si se encuentra D, conviértalo en Y y muévase a la derecha al paso 6.
• Paso 6: siga ignorando D y Z y muévase hacia la derecha. Convierta C en Z y muévase a la izquierda y vaya al paso 7.
• Paso 7: siga ignorando D y Z y muévase hacia la izquierda. Si encuentra Y, ignórelo, muévase a la derecha y vaya al paso 5.
• Paso 8: Sigue ignorando D, Y y A y muévete hacia la izquierda. Ignore X, mueva a la derecha y vaya al paso 9.
• Paso 9: Convierta A en X y muévase a la derecha y vaya al paso 10.
• Paso 10: 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 11. Si D, conviértalo en Y, muévase a la derecha y vaya al paso 8.
• Paso 11: 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, Q8, Q9, Q10 muestra el estado de transición y Q7 y Q11 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. Y, cuando se encuentre Y, ignórelo y vaya a la derecha y al estado Q4.
• 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 Y y muévase a la derecha. Si encuentra Z, ignórelo, muévase a la izquierda hasta el estado Q6. Si encuentra D, conviértalo en Y y muévase a la derecha hasta Q5.
• En el estado Q5, ignore todo D, Z y muévase a la derecha. Si encuentra C, haga que Z muévase a la izquierda hasta el estado Q6
• En Q6, ignore todo D, Z y muévase a la izquierda. Si encuentra Y, ignórelo y muévase a la derecha hasta el estado Q4.
• Si se alcanza el estado Q7, se producirá el resultado de la aceptación de la string.
• En Q8, ignore todo A, Y, D y muévase a la izquierda. Si encuentra X, ignórelo, muévase a la derecha hasta el estado Q9.
• En el estado Q9, si A encuentra, haga que X se desplace a la derecha al estado Q10
• En Q10, ignore todo A, Y y muévase a la derecha. Si se encuentra D, conviértalo en Y y muévase a la derecha hasta el estado Q8. Si se encuentra B, ignórelo y muévase a la izquierda hasta Q11.
• Si se alcanza el estado Q11, 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