Hace poco discutiendo con estudiantes del curso de Lenguajes Formales y de Programación sobre la implementación de un Autómata Finito Determinista (AFD), que tenían que hacer para el proyecto de curso, algunos no estaban realizando una "máquina de estados" y se estaban complicando en la programación. Así que implemente en Angular un ejemplo sencillo para poder ilustrar una propuesta de solución para programar el autómata.
En el siguiente enlace hay una descripción general de los autómatas finitos deterministas.
Buscamos poder reconocer palabras que sean aceptadas por el lenguaje regular, para esto leeremos carácter por carácter moviéndonos dentro del autómata.
AFD
Q = { A, B, C, D, E }
A
Σ = { 0, 1}
F = { C }
Función de transición
∂(A, 0 ) = B | ∂(A, 1 ) = C | |
∂(B, 0 ) = D | ∂(B, 1 ) = C | |
∂(C, 0 ) = D | ∂(C, 1 ) = C | |
∂(D, 0 ) = D | ∂(D, 1 ) = E | |
∂(E, 0 ) = D | ∂(E, 1 ) = C |
Procedimiento
- Carácter por carácter se realizará el reconocimiento de la cadena, y de esta manera se harán las transiciones en el autómata.
- El autómata es determinista, no hay ambigüedad en la función de transición.
- Solo debemos de programar la función de transición. Para esto nos ayudará
- Llevar el control del estado actual.
- Realizar una concatenación de los caracteres que se van leyendo.
- Programar una función que pueda cambiar el estado actual de acuerdo a la función de transición.
- Manejar errores:
- Si el carácter no pertenece al alfabeto.
- Si no hay una transición válida con un símbolo.
- Revisar si el estado donde nos encontramos es un estado de aceptación para determinar si la cadena es válida.
Ejemplo sencillo en angular
- npm install
- Instalará todas las dependencias del proyecto.
- ng serve
- Ejecutará un servidor local que pueden acceder en http://localhost:4200/
No hay comentarios:
Publicar un comentario