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...
Para la realización de este problema, hemos utilizado la ventaja de marcaje de símbolos.
El cabezal, se coloca en el primer 0 de la cadena, el de mas a la izquierda.
Funcionamiento:
En q0 marcamos el primer cero sin marcar que se encuentra.
En q1 se va hasta el primer 1, y si se encuentra B en vez de un 1 es que ya hemos comprobado toda la cadena.
En q2 se marca tambien el primer 0 sin marcar y se va a q3.
Entre q3 y q4 se coloca el cabezal otra vez en el primer 0 sin marcar del primer bloque.
Si en q0 se recorre la primera cadena entonces es porque el primer bloque es mas pequeño o igual que el segundo, asi que vamos a q5.
En q5 y q6 se desmarca el segundo bloque y se coloca el cabezal en el 1 que separaba los dos bloques.
Si en q5 se llega al B entonces tambien se acaba la cadena por lo que la cadena de bloques de 0 esta ordenada.
No hay comentarios:
Publicar un comentario