lunes, 14 de septiembre de 2020

Programando un Automata Finito Determinista en Angular

 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 

Tomando una expresión regular ( 0 | ( 0* 1)* ) 1 la cual está representada por el siguiente autómata:

  1. Q = { A, B, C, D, E } 

  2. A

  3. Σ = { 0, 1}

  4. F = { C }

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

En términos generales lo que buscamos es programar una máquina de estados para esto:
  • 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. 
Si logramos programar el autómata generalizando toda la definición formal no importará lo complejo de este, la programación no variará. 

Ejemplo sencillo en angular 

El código fuente se encuentra en el siguiente enlace:  https://github.com/sierra-oe/FDA-Angular-token

Para ejecutarlo recuerden:
  • npm install
    • Instalará todas las dependencias del proyecto. 
  • ng serve 
    • Ejecutará un servidor local que pueden acceder en http://localhost:4200/ 

Para cambiar el autómata a evaluar solo debe cambiar la definición del mismo y la tabla de transiciones. 




No hay comentarios:

Publicar un comentario

Arch linux actualización a Jenkins 2.337 - java 11

 Hace poco estaba instalando jenkins de manera local en mi ArchLinux, para esto utilice  los pasos en la documentación oficial. Jenkins func...