Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
Juan Jesús de la Cruz nos consultaba como resolver un Autómata para el siguiente planteamiento: Se requiere construir un autómata para reconocer cadenas, cuyo número de ceros sea divisible entre 3 y el número de unos sea divisible entre 5.
¿Cómo llego a obtener S que son los estados y F que es el estado final?
Para comenzar compartimos algunas publicaciones realizadas sobre los Autómatas.
- Autómatas de Estado Finito
- Ejemplos de Autómatas
- Diagrama de Transición (Autómatas)
- Guía de Autómatas Finitos Deterministas
Autómata Reconocer Cadenas de Ceros y Unos. Solución # 1.
Primera propuesta, verán que aún tiene errores.
Este es el Diagrama de Transición propuesto, puede mejorarse. Fue la primera solución que dimos antes que llegara la iluminación y completarlo con éxito.
En las entradas podemos ver que esta propuesta deja pasar algunas cadenas que no deberían ser aceptadas.
![]() |
Primera solución del Diagrama de Transición |
Símbolos y Estados del Autómata Solución # 1.
En el caso de esta propuesta inicial los estados quedan de la siguiente forma:
Gramática A = {0,1}
Estados S = {q0, q1, q2, q3}
Estados Finales F = {q0, q1, q3}
Estado inicial q1 = {q0}
Propuesta final, esta sería la solución correcta.

Ahora si vemos que el Autómata solo acepta cadenas de 3 ceros y 5 unos, todas las demás cadenas son rechazadas.


Autómata Reconocer Cadenas de Ceros y Unos. Solución # 2.
Propuesta final, esta sería la solución correcta.
Mucho puede pasar mientras vamos de viaje en el autobús, en este caso no podía concentrarme en disfrutar del viaje por el mencionado Autómata que propuso resolver Juan Jesús, uno de nuestros lectores. Me propuse dar solución mejorada y este fue el resultado de mis apuntes expres en el autobús.

Borrador del diagrama
Realizado en JFlap el segundo Diagrama de Transición lo dejamos así.
Autómata Ceros y Unos Creado en JFlap.
![]() |
Diagrama de Transición con ventana de pruebas. |

Autómata desarrollado de forma correcta.
El truco fue encontrar la forma de definir los estados finales, y resultó que el problema se resolvía perfectamente dejando como estado final el mismo estado inicial, pero con los retornos que podemos ver en la figura.
Ventana de pruebas.

Pruebas realizadas de forma correcta.
Símbolos y Estados del Autómata Solución Correcta.
Gramática A = {0,1}
Estados S = {q0, q1, q2, q3, q4, , q5, , q6}
Estados Finales F = {q0} también se le conoce como qf
Estado inicial q1 = {q0}
Gramáticas Válidas
000
11111
00011111
11111000
00011111000
1111100011111
00000011111
111111111100011111000
Etc.
00000011111
111111111100011111000
Etc.
Gramáticas Inválidas
0
00
000
1
11
111
1111
0011111
1111000Si tienes alguna opinión o otra propuesta de solución puedes dejarnos comentarios que apreciaremos mucho.
Si tienes algún ejemplo de autómatas y quieres compartirlo escríbenos en nuestro formulario de contactos, lo compartiremos en el blog.
No hay comentarios
Gracias por su comentario