Construya una máquina de Turing para un lenguaje L = {aibjck | i<j<k o i>j>k} ∩ {aibjck | i>j>k o i>j>k}

Prerrequisito – Máquina de Turing

El lenguaje L = {a ⁱ b ^j c ^k | yo < j < k o yo > j > k} ∩ {a ^yo segundo ^j c ^k | i > j > k o i > j > k} es lo mismo que los idiomas L={a ⁱ b ^j c ^k | j > max(i, k)} 
En este lenguaje, 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. 
 

• 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’.
• Y, el conteo de los 3er símbolos debe ser al menos 1. ‘a’ y ‘b’ pueden tener a partir de entonces 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 ‘
• En conclusión: el conteo del segundo símbolo debe ser mayor que el máximo del conteo del 1er y 3er símbolo y el conteo del 1er y 3er símbolo puede o no ser igual
  1. Comparar dos elementos haciendo dos elementos como un solo elemento.
  2. Si |Segundo| es mayor que max(|First|, |Third|), entonces se acepta.
  3. De lo contrario no se acepta.
  4. 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. 
      
  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.
  6. Paso 3: sigue ignorando D y Z y muévete hacia la derecha. Si se encuentra C, conviértalo en Z y muévase hacia la izquierda al paso 4. Si se encuentra B, ignórelo, muévase hacia la izquierda y vaya al paso 8.
  7. Paso 4: siga ignorando Z, A, Y y D y muévase hacia la izquierda. Si se encuentra X, ignórelo, muévase a la derecha y vaya al paso 1.
  8. Paso 5: Sigue ignorando Y y muévete hacia la derecha. Si se encuentra D, conviértalo en Y y vaya a la derecha al paso 6.
  9. Paso 6: sigue ignorando D y Z y muévete hacia la derecha. Convierta C en Z y muévase hacia la izquierda y vaya al paso 7. Si B Ignóralo, muévete a la izquierda y ve al paso 11.
  10. Paso 7: Sigue ignorando D y Z y muévete hacia la izquierda. Si se encuentra Y, ignórelo, muévase a la derecha y vaya al paso 5.
  11. 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. Si D ignora y muévete a la derecha y ve al paso 11
  12. Paso 9: Convierta A en X y muévase a la derecha y vaya al paso 10.
  13. Paso 10: sigue ignorando Y y A y muévete hacia la derecha. Si D, conviértalo en Y, muévase a la derecha y vaya al paso 8.
  14. Paso 11: detenga la máquina (se acepta la string).
  15. 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.
  16. 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.
  17. En Q2, ignora todo D, Z y muévete a la derecha. Si encuentra B, ignórelo, muévase a la izquierda y vaya al estado Q4, si encuentra C, haga que Z muévase a la izquierda y vaya a Q3.
  18. En el estado Q3, ignora todo Z, D, Y, A y muévete a la izquierda. Si encuentra X, ignórelo, muévase a la derecha a Q0.
  19. En Q4, ignora todo Y y muévete a la derecha. Si se encuentra D, conviértalo en Y y muévase a la derecha hasta Q5.
  20. En el estado Q5, ignora todo D, Z y muévete a la derecha. Si se encuentra C, haga que Z muévase a la izquierda al estado Q6. Si se encuentra B, ignore muévase a la izquierda al estado Q7
  21. En Q6, ignora todo D, Z y muévete a la izquierda. Si encuentra Y, ignórelo y muévase a la derecha al estado Q4.
  22. Si se alcanza el estado Q7, se producirá el resultado de la aceptación de la string.
  23. En Q8, ignora todo A, Y, D y muévete a la izquierda. Si encuentra X, ignórelo, muévase a la derecha hasta el estado Q9. Si se encuentra B, ignórelo y muévase a la derecha a Q11.
  24. En el estado Q9, si A encuentra, haga que X se desplace a la derecha al estado Q10
  25. En Q10, ignora todo A, Y y muévete a la derecha. Si D encontró, conviértalo en Y y muévase a la derecha hasta el estado Q8.
  26. Si se alcanza el estado Q11, se producirá el resultado de la aceptación de la string.