M.T. simple reconocedora de bloques de 0's ordenados ascendentemente

Al recibir una cadena de entrada de bloques de 0's separados por 1's, debe aceptar las cadenas que sus bloques de 0's estén ordenados de forma ascendente, es decir, aceptar las cadenas tipo ...B0010010000100000B... y rechazar cadenas como ...B001000100100000B...

Cadena de entrada: B0010001000B

Cadena de salida:    B0010001000B (cadena aceptada)

Cadena de salida:    BBBBBBBBBBBB (cadena rechazada)

 El funcionamiento es el siguiente:

1. Recorre la cadena de entrada marcando los primeros 0's de cada bloque hasta llegar al final, marcando siempre el primero que encuentra con el simbolo Y. (q0, q1, q2)
2. Vuelve atrás hasta el símbolo Y y repite el paso 1.  (q3)
3. Si en el primer marcaje (q0) encuentra un 1, sigue al siguiente bloque, si encuentra un B, la cadena es válida y la recorre para cambiar todos los X e Y por 0's (q4)
4. Si en el segundo marcaje o sucesivos (q1) encuentra un 1 o un B, la cadena no es válida y la recorre borrando todos los símbolos (q5, q6)

En esta M.T. se ha usado el alfabeto {0,1,B,X,Y}. Se asume que la posición inicial es el primer símbolo de la cadena de entrada. Si tan sólo debiera rechazar la cadena y no dejarla a 0's se pueden comentar todos los estados q5 y q6 y f(q1,1), f(q1,B).