Compilador Y Su Estructura

TEMA:

La minimización de AFD y los teoremas que están inmersos en la eliminación de estados inaccesibles

RESUME:

Explica los fundamentos teóricos del algoritmo de minimización y ver su funcionalidad sobre un ejemplo ya que en la minimización de un AFD existen dos estados que nos permite identificar en estados equivalentes al unirse en un solo estado esta unión de estados nos implica la unión tanto de sus transacciones de entrada como los de salida, una aplicación inmediata de esta aplicación es la equivalencia de la expresiones regulares, el algoritmo de minimización de autómatas finitos deterministas permite simplificar el manejo de autómatas. Se presenta aquí los detalles de este algoritmo y un ejemplo concreto. Se busca facilitar el entendimiento del algoritmo, en particular en estudiantes de cursos de compiladores o en profesionales que busquen la referencia al tema.

MARCO TEÓRICO:

Minimización de un AFD

Dos estados de un autómata finito determinista son estados equivalentes si al unirse en un sólo estado, pueden reconocer el mismo lenguaje regular que si estuviesen separados. Esta unión de estados implica la unión tanto de sus transiciones de entrada como de salida. Si dos estados no son equivalentes, se dice que son estados distinguibles. Un estado final con un estado no-final nunca será equivalentes.

Un AFD está minimizado, si todos sus estados son distinguibles y alcanzables. Un algoritmo de minimización de AFD es el siguiente:

1. Eliminar los estados inaccesibles del autómata.

2. Construir una tabla con todos los pares (p, q) de estados restantes.

3. Marcar en la tabla aquellas entradas donde un estado es final y el otro es no-final, es decir, aquellos pares de estados que son claramente distinguibles.

4. Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):

1. Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto marcar la entrada (p, q).

2. De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).

5. Agrupar los pares de estados no marcados.

Luego del tercer paso, si la tabla creada queda completamente marcada, entonces el AFD inicial ya era mínimo.

La complejidad computacional del problema de minimizar un AFD es polinomios. De hecho, existen algoritmos más eficientes aún que el mostrado en este artículo (aunque menos intuitivos). Sin embargo, el problema de minimizar un autómata finito no determinista es NP-completo y PSPACE-completo.

Ejemplo

En la primera figura del ejemplo, se muestra un autómata con el estado inaccesible d, el cual puede eliminarse inmediatamente. Luego se construye la tabla de pares de estados, y a continuación se marcan, de acuerdo a la tercera línea del algoritmo, las filas y columnas correspondientes a los estados finales c y g, salvo la celda que representa el par (c,g), puesto que al ser ambos estados finales, pueden ser estados equivalentes. Posteriormente, se marcan las celdas restantes de acuerdo a la cuarta línea del algoritmo, notando que el par (b, f) queda asociado con el par (c, g), y así finalmente se obtiene el autómata final, agrupando los estados b y f, así como c y g, tal y como se muestra en la segunda figura del ejemplo.

Minimización de un AFD.

AFD con estados redundantes.

AFD minimizado.

Tablas para la búsqueda de estados equivalentes

b

c

e

f

g

a b c e f

b

c

e

f

g

a b c e f

b

c

e

f

g

a b c e f

Generalizaciones de autómatas finitos

Existes diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentar su uso y expresividad. Así, por ejemplo, se definen los transductores de estados finitos como autómatas finitos que están dotados además de un alfabeto de salida, distinto al de entrada, y que pueden poseer más de un estado inicial.Las máquinas de Moore y máquinas de Mealy son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar sistemas secuenciales.

Es incluso posible aumentar el poder de cómputo de un autómata finito, permitiendo un alfabeto adicional sobre éste, que actúe sobre una memoria de tipo pila para ser considerada en cada transición. Esta es la idea utilizada por los llamados autómatas con pila,

...