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. 

Automátas Finitos Deterministas y no Deterministas

Los autómatas finitos son máquinas de estados que nos pueden ayudar a reconocer palabras que sean válidas en un lenguaje regular. Su funcionamiento básico es realizar transiciones de acuerdo a una función de transición que indica hacia dónde se mueve el autómata. 

A partir del estado inicial mediante símbolos de entrada el autómata realiza transiciones para poder aceptar o no un conjunto de caracteres. El autómata está definido de la siguiente manera   A = (Q, Σ, ∂, S1, F) donde: 

• Q: conjunto de todos los estados del automáta. 
• Σ: alfabeto del lenguaje regular, conjunto de todos los símbolos que pertenecen a este. 
• ∂: función de transición, nos indica las transiciones que realiza el autómata dado el símbolo que se esté analizando. 
• S1: estado inicial. No necesariamente debe utilizarse "S1", puede utilizarse el nombre que se desee. 
• F: conjunto de estados de aceptación o estados finales. Si al finalizar las transiciones el autómata termina en uno de estos estados entonces se acepta la cadena. 

El objetivo del autómata finito en general es reconocer si una palabra es válida o no para un lenguaje regular. 

Autómatas finitos deterministas (AFD)

Los autómatas finitos deterministas tienen la característica de que para una entrada solo hay un posible movimiento a otro estado, es decir no hay dos posibilidades de transición con el mismo símbolo para un estado. Por ejemplo:

Automatas finitos no deterministas (AFND)

A los autómatas que tienen ambigüedad o que pueden realizar un transicion a dos estados distintos con el mismo símbolo le llama autómata finito no determinista

Ejemplo: 

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

 

Diagrama del autómata finito determinista

Para generar los autómatas a partir de expresiones regulares se puede utilizar el método del árbol y el de Thomson.