Para la máquina de Turing clasica, en el estado q0 marcamos con una X el primer 0 y cambiamos al estado q1, ignora los 0 y va recorriendo la cadena hasta que encuentra un 1 que cambia de nuevo de estado a q2. Recorre hacia la derecha la cadena saltandose todos los posibles X's (si lo hubiera) hasta que encuentra un o, momento que lo sustituye por una X y mueve el cabezal hacia la izquierda cambiando de estado a q3. Si hay X's por su camino hacia la izquierda se los salta hasta que lee un 1, cambiando de estado a q40 y moviendose a la izquierda. Recorre todos los 0´s que pueda encontrarse el cabezal hasta que lee un X, momento que se desplaza a la derecha y cambia de estado a q0. Repite el proceso todo el tiempo que encuentre parejas del grupo de 0's inicial y el grupo de 0's contiguo hasta que estando en q0 encuente 1, momento que significa que la cadena de 0's se ha agotado, pasamos a q5 y recorremos el siguiente grupo de 0's que estabamos analizando también para comprobar que aún le quedaban 0's que tachar, una vez comprovado que aún quedaban ceros nos vamos a q6 para movemos al inicio de esa cadena y dejando las X's marcadas en 0's para dejarla lista para la siguiente comprobación entre ese grupo de 0's y el siguiente.
Si estando en q1 encuentra el blanco, significando que no hay grupo de 0's a la derecha del actual terminando con éxito la MT clásica en el estado q7.
ENTRADA: ...B01001000100000B...
FINALIZA: Acepta si los grupos de o's separados por 1's están ordenados por orden creciente.
| 0 | 1 | X | B | |
| q0 | (q1,X,R) | (q5,1,R) | ||
| q1 | (q1,0,R) | (q2,1,R) | (q7,B,L) | |
| q2 | (q3,X,L) | (q2,X,R) | ||
| q3 | (q4,1,L) | (q3,X,L) | ||
| q4 | (q4,0,L) | (q0,X,R) | ||
| q5 | (q6,0,L) | (q5,X,R) | ||
| q6 | (q0,1,R) | (q6,0,L) | ||
| q7 |
No hay comentarios:
Publicar un comentario