Una FSM (máquina de estados finitos) puede considerarse una máquina de Turing de longitud de cinta finita
(A) sin capacidad de rebobinado y movimiento de cinta unidireccional
(B) capacidad de rebobinado y movimiento de cinta unidireccional
(C) sin capacidad de rebobinado y movimiento de cinta bidireccional
(D ) capacidad de rebobinado y movimiento de cinta bidireccional
Respuesta: (A)
Explicación: una FSM (máquina de estados finitos) puede considerarse una máquina de Turing de longitud de cinta finita que no tiene capacidad de rebobinado y es un movimiento de cinta unidireccional.
El rebobinado es un procedimiento en el que el primer elemento de entrada va al último elemento de la cinta, lo procesa y vuelve al inicio de la cinta de entrada.
Esto lo hace solo la máquina de Turing porque la máquina de Turing puede moverse en ambas direcciones, por lo que también se denomina bidireccional.
En FSM, la entrada se mueve de izquierda a derecha, uno por uno, pero no se puede rebobinar.
La opción (A) es correcta.
Cuestionario de esta pregunta
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