Una máquina de Turing M de una sola cinta tiene dos estados q0 y q1, de los cuales q0 es el estado inicial. El alfabeto de cinta de M es {0, 1, B} y su alfabeto de entrada es {0, 1}. El símbolo B es el símbolo en blanco que se usa para indicar el final de una string de entrada. La función de transición de M se describe en la siguiente tabla
| 0 | 1 | B | |
| q0 | q1, 1, R | q1, 1, R | Detener |
| q1 | q1, 1, R | q0, 1, L | q0, B, L |
La tabla se interpreta como se ilustra a continuación.
La entrada (q1, 1, R) en la fila q0 y la columna 1 significa que si M está en el estado q0 y lee 1 en el cuadro de cinta actual, entonces escribe 1 en el mismo cuadro de cinta, mueve su cabezal de cinta una posición hacia el derecha y transiciones al estado q1.
¿Cuál de las siguientes afirmaciones es verdadera acerca de M?
(A) M no se detiene en ninguna string en (0 + 1)+
(B) M no se detiene en ninguna string en (00 + 1)*
(C) M se detiene en todas las strings que terminan en 0
(D) M se detiene en todas las strings que terminan en 1
Respuesta: (A)
Explicación:
Cada vez que se proporciona B como entrada, la máquina se detiene. Esto implica que epsilon solo se acepta cuando B aparece como entrada.
En cierre positivo, epsilon no está presente. Entonces, la máquina de Turing nunca se detiene en caso de (0+1) + .
Por lo tanto, la opción (A) es correcta.
Comente a continuación si encuentra algo incorrecto en la publicación anterior.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA