Esta MT acepta cadenas con bloques de 0's separados con 1's, ordenados en orden creciente. Es decir, aceptará las cadenas del estilo ...B01001000B... y no aceptará aquellas del estilo...B01000100B...
Hemos elegido multicabezal porque así analizamos dos bloques de 0's a la vez, por lo que es mucho mas simple y rapido.
Situacion inicial: Ambos cabezales en el primer 0 de la cadena, el de mas a la izquierda.
Funcionamiento:
En q0 dejamos un cabezal en el primer bloque de 0's y el otro lo movemos al segundo bloque de 0's.
En q1 vamos recorriendo los dos bloques mientras hayan 0's en los dos bloques, o si hay dos 1's (mismo numero de 0's en ambos bloques).
Si se llega a la situación de que en el primer cabezal tenemos 1 y en el segundo 0, significa que el primer bloque es mas pequeño por lo que pasamos a q2 y colocamos los cabezales para analizar el siguiente grupo de bloques de 0's.
Si en q1 o en q2 llegamos a la situación de que el segundo cabezal lee un B, es porque hemos recorrido toda la cadena y está ordenada.
No hay comentarios:
Publicar un comentario