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 = {q₀, q_1, q_2,  q₃}

Estados Finales         F = {q₀, q_1,  q₃}

Estado inicial            q₁ = {q₀}

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

Autómata  Ceros y Unos Creado en JFlap.

Realizado en JFlap el segundo Diagrama de Transición lo dejamos así.

Diagrama de Transición con ventana de pruebas.

Si no tienes JFlap puedes leer aquí.

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 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 = {q₀, q_1, q_2,  q_3,  q4, _,  q5, _,  q6}

Estados Finales         F = {q₀}  también se le conoce como qf

Estado inicial            q₁ = {q₀}

Gramáticas Válidas

000

11111

00011111

11111000

00011111000

1111100011111
00000011111
111111111100011111000
Etc.

Gramáticas Inválidas

0

00

000

1

11

111

1111

0011111

1111000

Si 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.