Cadena de entrada: B0010001000B
Cadena de salida: B000B
En la M.T. construida, se han tenido en cuenta dos casos más. La posibilidad de que se encuentre un 1 al principio o un 1 al final:
B1001000100B
B0010001001B
En caso de no considerarse cadenas válidas, tan sólo debería eliminarseel estado q0 para que no acepte el 1 inicial y la f(q5,1) para que no acepte el 1 final.
El funcionamiento básico del autómata es el siguiente:
- Borra todos los 0's hasta encontrarse un 1 (BBB10001000B)
- Borra ese 1 y se mueve al final (BBBB0001000Bq3B)
- Una vez encontrado un B salta a la derecha y anota un 0 (BBBB0001000B0B)
- Vuelve y repite la operación hasta encontrar un blanco después de tachar 0's (BBBBBBBBBBBB000B)
Como se puede ver, el alfabeto utilizado vuelve a ser {0,1,B}. Además suponemos que la posición inicial del autómata se sitúa en el primer símbolo de la cadena de entrada.
EDITADO: Se ha modificado la M.T. para que acepte cadenas B00011100B. Si no se debieran aceptar, tan sólo habría que eliminar el estado f(q7,1)
2 comentarios:
Hemos probado esta MT con varias cadenas y parece que solo falla cuando le pasas cadenas que empiezan por "11". Según hemos visto vuestra MT interpreta el "11" al principio de la cadena como un bloque de 0's. El resto de maravilla.
Publicar un comentario