Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos - Api Developer: Lenguajes de Programación y Compiladores

Api Developer: Lenguajes de Programación y Compiladores

Lenguajes de Programación y Compiladores

Hot

Post Top Ad

miércoles, 12 de julio de 2017

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ómata 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.

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
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}



Autómata 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.

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
Borrados del diagrama

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

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
Diagrama de Transición con ventana de pruebas.


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

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
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.

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
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.

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.

Derechos Reservados. Postecnologia.com. Con tecnología de Blogger.

Post Top Ad