Autómatas Finitos Determinísticos [C#]

Autómatas Finitos Determinísticos

Bueno, en esta ocasión trataré de explicar algunas cosas sobre los autómatas finitos:

  • ¿Qué necesito saber?
  • ¿Qué son las expresiones regulares?
  • ¿Qué son los autómatas finitos?
  • ¿Como funcionan?
  • Programando nuestro autómata

También les mostraré una forma de crear una especie de biblioteca de autómatas en un solo programa, para no tener que hacer una aplicación para cada autómata que deseemos crear. Creo que esto será de gran utilidad, ya que en mi caso, en la universidad cuando lleve la materia de Teoría de la Computación y toco el turno al tema de Autómatas Finitos, me vi en la necesidad de crear una aplicación por autómata y la verdad no es nada practico visto desde varios puntos de vista:

  • Al funcionar de la misma manera, reescribí el mismo código muchas veces
  • Cuando buscaba algún autómata en especifico era difícil encontrarlo

Bien, para no hacer esto más largo de lo que debería empecemos.

¿Qué necesito saber?

Bien, antes de pasar al siguiente punto debemos tomar en cuenta las siguientes definiciones:

Expresión Regular: Representa un patrón o una secuencia de símbolos tomados de un alfabeto con un orden en específico
Lenguaje: Conjunto de todas cadenas formadas a partir de un alfabeto.
Alfabeto: Es el subconjunto finito y no vacío de símbolos tomado del conjunto universo formado por cada uno de los símbolos que pertenecen a un lenguaje.
Cadena: Es cualquier secuencia finita de símbolos construida con símbolos de un alfabeto.
Longitud de cadena: Es el número de símbolos concatenados que forman una cadena
Cadena vacía: Representa una cadena de longitud cero y se representa con el símbolo ε (Épsilon).

No se trata de que las aprendamos de memoria, de hecho no me las se de memoria, simplemente las entiendo y formo mi propia definición.

¿Qué son las Expresiones Regulares?

Nota: Antes que nada quiero pedirles que cuando haga referencia a una cadena se olviden de los Strings, ya que a lo que me refiero con cadena es a un conjunto de símbolos cualquiera y no a un String en un lenguaje de programación.

Una expresión regular lo que hace es evaluar o validar una cadena de entrada y nos indica si es valida para dicha expresión regular, si fuera valida la salida seria un “SI” y en caso contrario un “NO”. Talves digas “ok, valida cadenas, pero… ¿Qué son esas cadenas?”, y de hecho es una muy buena pregunta, si la expresión regular nos dijera que es una cadena valida significa que la cadena es un token. Dejenme darles una definición de token:

[Wikipedia*]Token: “Un token es una cadena de símbolos que tiene un significado en un lenguaje”

Bien, veamos, entonces un token es una cadena de símbolos que tiene un significado, pero ¿Qué significado?, pues dependeria del token mismo, es decir, en un lenguaje de programación los tokens serian las palabras reservadas como if, then, else, for, foreach, char, int, float, etc. o también podrian ser constantes numéricas como 1, 657, 3.1415926535897932384626433832795. Para nosotros no son mas que cadenas, pero para la computadora tienen un significado diferente, un if le dice a la computadora que si se cumple alguna condición realice una operación, que ¿significado tiene?, pues una orden para la computadora y las constantes numéricas pues son valores numéricos como tal y le indican a la computadora que los trate como tal. Todos sabemos que la computadora se maneja en base al sistema binario, es decir, 0’s y 1’s, la computadora almacena en memoria las palabras reservadas if, then, else, for, while, como números binarios, pero debido al significado que tienen no las maneja como números, sino como instrucciones u ordenes y a las constantes numéricas las maneja como números. A esto nos referimos cuando decimos que tienen un significado. Pero recuerden que esto es un ejemplo.

Para denotar una expresión regular existen algunos sisímbolos que debemos conocer y saber que significan. (¿Tokens para describir tokens?)

Tokens para Expresiones Regulares

Algúnos ejemplos de expresiones regulares serian:

  • Digito -> ( 0 | 1 | 2 | 3 | 3 | 4 | 5 | 6 | 7 | 8 |9 )
  • Vocal -> ( a | e | i | o | u)
  • NumDec -> Digito+ . Digito+
  • El primero nos dice que el token Digito es un 0 o un 1 o un 2 o un 3 o un 4 o un 5 o un 6 o un 7 o un 8 o un 9.
  • El segundo nos dice que el token es una letra que puede ser una “a” o una “e” o una “i” o una “o” o una “u”.
  • El tercero nos dice que el token NumDec (Número decimal) esta formado por: uno o más Digitos, un punto (.) y uno o más Digitos.

¿Qué son los Autómatas Finitos?

Bien, ahora veremos lo que son los autómatas finitos, no son nada más que reconocedores de cadenas o mejor dicho, de tokens. La forma de representar los autómatas finitos es la siguiente:

Ejemplo de Autómata Finito Deterministico

S: Es el estado inicial de nuestro autómata, por lo general es un 0 o un 1.
F: Es el estado final o de aceptación al que llegará nuestro autómata si la cadena fue aceptada. Pueden existir más de un estado de aceptación, de ser asi, F seria el conjunto de estados de aceptación y existiría un nodo por cada uno de ellos.
X: Es el símbolo que pertenece al alfabeto de la expresión regular con el que el autómata cambia de estado.

Existen dos tipos de autómatas finitos, cada uno con sus características que son las que a continuación se describen:

Autómata Finito Determinístico [AFD]

  • Tiene un nodo o estado inicial y al menos un nodo o estado final.
  • Cada arco (flecha) debe estar etiquetado con un símbolo que pertenece al alfabeto.
  • No puede haber arcos etiquetados con la cadena vacía (ε).
  • No pueden existir arcos que tengan la misma etiqueta.

Autómata Finito No Determinístico [AFND]

  • Tiene un nodo o estado inicial y al menos un nodo o estado final.
  • Cada arco (flecha) debe estar etiquetado con un símbolo que pertenece al alfabeto o con la cadena vacía (ε).
  • No pueden existir arcos que tengan la misma etiqueta.

La definicion formal de un autómata es la siguiente:

AF = (K, ∑, Δ, S, F)
K: Conjunto finito de estados.
∑: Conjunto finito de símbolos que podrá leer el autómata, también llamado alfabeto de entrada.
Δ: Es la función de transición con la que el autómata cambia de estado K con un símbolo ∑ del alfabeto. (K x ∑ →K)
S: Es el estado inicial, y esté pertenece a K.
F: Es el conjunto de estados finales o de aceptación, estos pertenecen a K.

¿Como funcionan los Autómatas Finitos?

Los autómatas tienen una funcion de transicion, pero ¿Qué es esto?, pues no es nada más que una tabla que tiene la relación Estado/Símbolo con la que cambia de un estado(no siempre cambiará de estado, esto depende de la expresión regular). Para mostrarles como se contruye haremos los autómatas para las expresiones regulares de ejemplo Digito y NumDec y les dejaré como tarea que contruyan el autómata para Vocal.

Recordemos la expresión regular.
Digito -> ( 0 | 1 | 2 | 3 | 3 | 4 | 5 | 6 | 7 | 8 |9 )

Ahora hagamos la definicion formal de nuestro automata Digito:

Digito = (K, ∑, Δ, S, F)

¿Cuantos estados tendrá el autómata?

Yo descubrí una formula para saber cuantos estados tendrá el autómata y funciona siempre y cuando no usemos el algoritmo de Thompson. Pero eso es harina de otro costal.

|K| = 1 + Ω

El 1 representa el estado inicial del automata al que le sumaremos Ω que son las características del token, en este caso al ser un solo digito solo tenemos una característica, asi que |K| = 2.

¿Cual es el estado inicial?

Pero nosotros tomaremos como estado inicial S el 0.

¿Cual será el conjunto de estados?

Si el estado inicial S será 0 y |K| = 2, esto quiere decir que el conjunto de estados será K = { 0, 1 }

y el estado de aceptación…. ¿Cual es?
El estado de aceptación sera el que corresponda a la ultima caraceterística de la expresión regular, en este caso solo tenemos una característica y el estado que le corresponde es el 1, asi que el estado de aceptación será 1.

Después de todo esto tenemos podemos decir que nuestro autómata y su representación gráfica seria:

Autómata Finito Deterministico para Números de un solo Digito

Digito = (K, ∑, Δ, S, F)

  • K = { 0, 1 }
  • = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
  • S = 0
  • F = { 1 }

Muy bonito Isaac, pero se te olvido la función de transición

Bien, para mi es más fácil hacer la tabla de transiciones ya con el diagrama del autómata hecho, ahora les explicaré como hacerla. La tabla tendrá un |K| renglones, es decir, uno por cada estado en el conjunto de estados y tendrá |∑| columnas, es decir, uno por cada símbolo en el alfabeto de entrada. La forma de llenarla será la siguiente:

Q(K,∑)=K’

Donde:
Q: Representa una celda en la tabla.
K: Es el estado actual del autómata.
: Es el símbolo que acaba de leer el autómata.
K’: Es el estado nuevo al que el autómata cambiará.

Como se muestra en la tabla siguiente, en la celda Q(0,0) = 1, ¿por que?, pues porque el autómata estando en el estado 0, y leyendo el símbolo 0 pasará al estado 1, y lo podemos comprobar en la gráfica del autómata. Podemos ver que en el nodo 0 sale un arco etiquetado con el símbolo 0 y va al estado 1. Repetiremos esto por cada arco que salga de cada nodo en el diagrama. Para las celdas que queden vacías, podemos dejarlas así, o poner un guión para representar que el autómata no cambiará de estado con esa condición de estado actual y símbolo leído.

Tabla de transicion

Programando Nuestro Autómata

Bien, ya sabemos que son y como funcionan los autómatas finitos, ahora veremos como programarlos, yo en este caso usare C#

Como les dije al inicio, les mostraré como hacer una especie de biblioteca de autómatas en una sola aplicación en la cual podamos indicar cual usar y ademas les mostraré una forma de no reescribir el código una y otra ves, ya que todos funcionan con la misma base.

Primero hagamos la interaz de usuario, yo daré una opcion, pero ustedes pueden mejorarla. yo usaré la siguiente:

Interfaz Grafica

Primero construiremos una clase abstracta que llamaremos AbstractAutomata, que sera la que contenga el funcionamiento base de un automata, y agregaremos otra clase llamada Digito que heredará de AbstractAutomata como se muestra en la siguiente imagen:

Clases

Como pueden ver en el diagrama de clases, AbstractAutomata tiene 3 atributos(campos):
Un arreglo de enteros que hará de conjunto de estados finales(_f).
Un entero que será el estado inicial del autómata(_s).
Un arreglo de enteros que será la tabla de transiciones(_stateTable).
A demás de eso tiene un constructor con el que le pasamos como parámetro el arreglo de estados finales y la tabla de transiciones, también por defecto establecemos _s = 0.

Código de AbstractAutomata

Nota: ¿Recuerdan las celdas de la tabla de transiciones que dejamos vacías o con un guión?, pues en nuestro arreglo las llenaremos con un -1, por que, pues por que los estados de un autómata están en el intervalo [0,∞), como pueden ver no comprende los números negativos, de ahí podemos inferir que podemos usar cualquier número negativo para indicar que no existe transición de estado con una convinacion de estado actual y símbolo leído dada.

También tiene un método GetState al que le pasamos como parámetro el estado actual(s) y el símbolo leído(c) y nos retorna el estado al que el autómata cambiará. Este método cambiara dependiendo del autómata, así que lo declaramos abstracto y no lo implementamos quedando así:

Código de GetState()

También tiene un método RecognizeToken que es abstracto, ya que, en mi caso, cuando la expresión regular llevaba por ejemplo Letra*, es decir ninguna letra o muchas, tenia que hacer algunas validaciones antes de entrar al algoritmo de reconocimiento, pues este es el propósito de que sea abstracto, que de ser necesario realizar alguna operación(como convertir el texto en minúsculas o mayúsculas por ejemplo) hacerlo sin modificar el algoritmo de reconocimiento del autómata. El código quedaria de la siguiente forma:

Código de RecognizeToken()

Ahora, el utimo método es el corazón del autómata, es el algoritmo de reconocimiento del token, este NUNCA cambiará, esta es una de las razones por la que hacemos la clase AbstractAutomata, para escribirlo solo una ves y que los autómatas hereden de ella este método que siempre será igual. Este método es protegido para que solo las clases hijas puedan verlo, y estas clases serán los autómatas que iremos haciendo, en este caso Digito y NumDec. El código será el siguiente:

Algoritmo de un Autómata

Este algoritmo realiza los siguientes pasos:

  • Lee un símbolo de la cadena de entrada.
  • Obtiene el nuevo estado para el autómata con el método GetState(K,∑).
  • Si no ha llegado al final de la cadena y GetState(K,∑) no es -1 (invalida) lee el siguiente símbolo, sino deja de analizar.
  • Si el estado actual esta en el arreglo de estados finales(_s esta en _F) la cadena es aceptada, en caso contrario la cadena es invalida.

Bien, ahora terminaremos la clase Digito, esto es mucho más fácil ya que en el constructor recibe el conjunto de estados finales(_F) y un arreglo con la tabla de transiciones(_stateTable), simplemente los pasamos al constructor base y listo:

Clase Digito

En este autómata no necesitamos hacer ninguna operación con la cadena de entrada antes de empezar con el algoritmo de reconocimiento, por lo tanto sobreescribiremos el metodo RecognizeToken y simplemente devolvera lo que retorne el método RecognizeBase de esta forma:Función RecognizeToken

Ahora solo nos falta el metodo GetState, es muy fácil este método, de hecho es un simple switch con el parametro c(switch(c)) que recibe, Aqui debemos agregar un case por cada símbolo del alfabeto de nuestro autómata, y por seguridad, debemos tomar en cuenta los errores intencionales y no intencionales del usuario, al final debemos poner una clausula default con la que atraparemós cualquier símbolo que no este dentro de nuestro alfabeto y nos dirá que es invalida con un default: return -1 como se muestra a continuación:

Función GetState ya implementada

Ahora les mostrare el código que escribí en la forma, creo que puedo suponer que no necesito explicarlo ya que no es algo fuera de lo normal, así que los dejare aquí, pero igual, cualquier duda pueden hacérmela saber y con gusto les explico, simplemente trato de no extender de más el post.

Ahora les toca a ustedes probar que funcione, yo ya lo he hecho y funciona al 100%, prueben ingresando números de un solo digito, y deben de ver el siguiente mensaje:

Tambíen prueben ingresando números de más de un digito o cualquier otra cosa como letras, números, signos, etc y deben ver este mensaje:

Bien, ahora solo nos falta hacer el autómata para NumDec, pero esta ves iremos más rapido, cualquier duda pueden regresar a los pasos anteriores y repasarlos. Primero debemos crear la clase NumDec de la forma que se muestra a continuacion:

Antes de continuar debemos ver como quedaria el diagrama del autómata, y seria de la siguiente forma:

Para que no quedara tan amontonado use “[0-9]” para indicar que hay una flecha por cada digito del 0 al 9.

Como pueden ver nuestro autómata quedo asi:

NumDec = (K, ∑, Δ, S, F)

K = { 0, 1, 2, 3}
= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, . }
S = 0
F: = { 3 }

Y la funcion de transicion seria esta:

Ahora estamos listos para programarlo, en el constructor de NumDec escribiremos exactamente lo mismo que en el de Digito

y también el método RecognizeToken es igual:

Lo unico que cambio es el método GetState que quedaria de la siguiente forma:

De hecho esto se puede resumir usando el método char.IsDigit, pero eso se los dejo a ustedes como practica de optimizacion de código. Ahora solo falta agregarlo a la lista de autómatas de la misma forma que el autómata digito:

Ahora les dejo unos ejemplos probando este autómata:

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

+ 61 = 71