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

Publicación traducida automáticamente

Artículo escrito por SHUBHAMSINGH10 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 *