A la hora de entender cómo funciona una MT ayuda (mucho :-)) saber cuál es la posición inicial del cabezal, cuál es la cadena de entrada, cuál es la cadena de salida, cuál es la idea básica...
Haciendo una traza con el ejemplo de cadena de entrada que proporcionais hemos encontrado varios fallos que no dejan continuar correctamente a la máquina.
Explicación de la traza: Suponiendo que empezaba en q0 recorremos hacia la derecha ignorando todos los 0's hasta que encuentra un 1, momento que pasa al estado q1. Al encontrar un 0 en q1 se "marca" el 0, cambia de restado a q2 y se desplaza hacia la izquierda. En q2 recorre todos los 0's y 1's que encuentre hasta el inicio de la cadena de entrada que se lee un B, momento que pasa a q3 y se desplaza a la derecha. En q3 el cabezal lee un 0, sustituyendolo por un "Y" y cambia al estado q0. En q0 vuelve a recorrer la cadena de 0's hacia la derecha hasta que encuentra un 1, cambiando de estado a q1. En q1 recorre los 0's "marcados" hasta que lee un 0 sin "marcar", momento que lo "marca", cambia de estado a q2 y se mueve hacia la izquierda. En q2 "casca" la MT al no poder saber qué hacer al leer 0's marcados... y auqnue estubiera corregido también cascaria porque no sabe qué hacer con las "Y".
2 comentarios:
A la hora de entender cómo funciona una MT ayuda (mucho :-)) saber cuál es la posición inicial del cabezal, cuál es la cadena de entrada, cuál es la cadena de salida, cuál es la idea básica...
O:-)
Haciendo una traza con el ejemplo de cadena de entrada que proporcionais hemos encontrado varios fallos que no dejan continuar correctamente a la máquina.
Explicación de la traza:
Suponiendo que empezaba en q0 recorremos hacia la derecha ignorando todos los 0's hasta que encuentra un 1, momento que pasa al estado q1.
Al encontrar un 0 en q1 se "marca" el 0, cambia de restado a q2 y se desplaza hacia la izquierda.
En q2 recorre todos los 0's y 1's que encuentre hasta el inicio de la cadena de entrada que se lee un B, momento que pasa a q3 y se desplaza a la derecha.
En q3 el cabezal lee un 0, sustituyendolo por un "Y" y cambia al estado q0.
En q0 vuelve a recorrer la cadena de 0's hacia la derecha hasta que encuentra un 1, cambiando de estado a q1.
En q1 recorre los 0's "marcados" hasta que lee un 0 sin "marcar", momento que lo "marca", cambia de estado a q2 y se mueve hacia la izquierda.
En q2 "casca" la MT al no poder saber qué hacer al leer 0's marcados... y auqnue estubiera corregido también cascaria porque no sabe qué hacer con las "Y".
Publicar un comentario