Un autómata es una máquina, ya sea real o virtual, que se utiliza para el reconocimiento de patrones, es decir, buscar una cadena de símbolos determinada de entre varias válidas. Una aplicación real es la construcción de compiladores, que como sabemos, comprueban que las palabras reservadas de las estructuras estén bien puestas (parte del análisis léxico).

     Como veremos, los autómatas finitos y los lenguajes regulares se encuentran en el nivel más bajo de la jerarquía de máquinas y lenguajes.

1.1. ANÁLISIS LÉXICO

     Vamos a seguir un ejemplo real para la descripción de un autómata: los nombres de variables en un lenguaje de programación cualquiera, los cuales están compuestos por una letra inicial seguidos por un conjunto finito de letras y números cualquiera.

     Cualquier estructura léxica en un lenguaje de programación (una cadena del programa fuente) termina con un conjunto de símbolos reconocidos como fin de la estructura; las llamaremos marcas de fin de cadena y pueden ser espacios, puntos y comas y retorno de carro. En la declaración de variables, recordemos que usamos comas para separar los nombres de variable.

     Como la descripción de un autómata en lenguaje natural puede ser ambigua si este es un poco complicado, necesitamos medios para representarlos de una forma exacta.

1.1.1. Diagramas de transiciones

     También llamado diagrama de estados o red de transiciones, es una representación gráfica del autómata, y está compuestos de:

     Decimos que el autómata representado por un diagrama de transiciones acepta una cadena si la secuencia de símbolos que aparecen en la misma (de izquierda a derecha) corresponde a una secuencia de arcos rotulados que conducen del círculo con apuntador a un círculo doble.

     A partir del diagrama de transiciones se puede hacer un programa que reconozca estructuras léxicas (cadenas válidas), aunque el resultado de la conversión no sea la mejor de las posibles soluciones.

     Se designa una variable para almacenar el estado actual y se inicializa como el estado inicial. Con una dentro de una sentencia WHILE (no sea fin de cadena), una sentencia CASE OF dirige las transiciones a otros estados, dando el estado siguiente mediante IF-THEN-ELSE anidados, dependiendo del símbolo leído. Si la cadena es inaceptable, el programa sale a una rutina de error.

1.1.2. Tabla de transiciones

Es una representación tabular (una tabla) del autómata donde la tabla tiene:

• N filas, una por cada uno de los n estados del diagrama de transiciones.
• Una columna por cada símbolo o categoría de los mismos posible en una cadena (estarán todos los símbolos o categoría de símbolos posibles).
• Una columna etiquetada como FDC (fin de cadena).
• El elemento de la tabla (m,n), estado m símbolo n, será el estado al que se llega desde un estado m a través de una arco (transición)con etiqueta n.
• Si no hay transición (arco) desde el estado m con el símbolo n, entonces el elemento (m,n) es la transición a un estado de error.
• En los elementos (m,FDC), si el estado m es de aceptación será aceptar, en caso contrario es error.

     Desde la tabla de transiciones también se puede hacer un programa, pero la solución es mejor, pues el algoritmo es el mismo para autómatas con el mismo número de estados y de símbolos, cambiando sólo el contenido de la tabla. Se asigna a una variable el estado inicial, que se actualizará con el elemento (variable, símbolo actual) que estará en memoria.

     El programa desde el diagrama de transiciones no es la mejor solución (si hay muchos estados, el CASE-OF puede ser interminable); Es mejor desde la tabla de transiciones.

© 1999 Roberto de la Fuente López. Todos los derechos reservados

Fecha de actualización: 15 de abril de 1999