MINIMIZACIÓN DE AUTÓMATAS FINITOS

MINIMIZACIÓN DE AUTÓMATAS FINITOS
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 estadosdistinguibles. 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:
Eliminar los estados inaccesibles del autómata.
Construir una tabla con todos los pares (p, q) de estados restantes.
Marcar en la tabla aquellas entradas donde un estado es final y el otro esno-final, es decir, aquellos pares de estados que son claramente distinguibles.
Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):
Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto marcar la entrada (p, q).
De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).
Agrupar los pares de estados no marcados.

Luego deltercer 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 polinomial. 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-completoTeorema:
Sea A un autómata finito determinista. Existe Â, AFD equivalente a A, con un número mínimo de estados, único salvo isomorfismo.
Proceso en varias etapas:
A – Estados equivalentes.
B – Autómatas equivalentes.
C – Isomorfismo de A.F.
D – Autómata mínimo.
A – Equivalencia de estados
Definiciones:
Sea A = (∑, Q, q0, f, F) un autómata finito determinista.
1.-Sean p, q ∈ Q. Se dice que py q son equivalentes

p E q ≡ ∀ x ∈ ∑* f (p,x) ∈ F ⇔ f (q,x) ∈ F 2.
2.-Sean p, q ∈ Q, k ∈ N. Se dice que p y q son equivalentes en longitud k o k-equivalentes
p Ek q ≡ ∀ x ∈ ∑* |x|≤k f (p,x) ∈ F ⇔ f (q,x) ∈ F
Notas:
1.-p E q significa que los dos estados evolucionan de manera paralela, funcionan igual, hacenlo mismo en el siguiente sentido:
f (p,x) ∈ F ⇔ f (q,x) ∈ F se puede escribir
f (p,x) ∈ F ⇒ f (q,x) ∈ F y
f (q,x) ∈ F ⇒ f (p,x) ∈ F
y puesto que la proposición p ⇒ q es lógicamente equivalente a ¬ q ⇒ ¬ p, se puede escribir
f (p,x) ∈ F ⇒ f (q,x) ∈ F y
f (p,x) ∉ F ⇒ f (q,x) ∉ F
es decir, para cualquier palabra, si desde p llega a un estado final, también desde q se llega aestado final y si desde p llega a estado no final, también desde q llega a estado no final.


2. La definición 1 no proporciona un procedimiento para saber si dos estados p,q ∈ Q son equivalentes, puesto que hay infinitas palabras x en ∑* , aunque el alfabeto ∑ sólo tenga un símbolo.
En cambio, para un determinado número natural k, si es posible, con la definición 2, saber si dos estados p,q ∈ Qson k-equivalentes, puesto que hay un número finito de palabras x ∈ ∑* cuya longitud es |x|≤ k.
No obstante, utilizar la definición 2 para ello, parece, cuando menos, muy pesado o laborioso.
3. Obviamente las relaciones binarias E y Ek son relaciones de equivalencia sobre el conjunto Q y determinarán una partición de Q, el conjunto cociente, que denotaremos de la siguiente forma:
Q/E sedenotará como PE
Q/Ek se denotará como Pk
4. En particular para k = 0, se tiene la partición Q/E0 = P0 de la siguiente forma
p E0 q ≡ ∀ x ∈ ∑* |x|≤ 0 f (p,x) ∈ F ⇔ f (q,x) ∈ F
⇔ f (p, λ) ∈ F ⇔ f (q, λ) ∈ F

λ es la única palabra |x|≤ 0
⇔ (p ∈ F ⇔ q ∈ F)

Definición de f,...