Minimización de estados de un AF

 

Minimización de un AFD

La minimización es un proceso que nos permite encontrar, para un dado autómata finito M, un autómata finito M’ con las siguientes propiedades: Si M y M’ comienzan por sus estados iniciales, producirán las mismas salidas para las mismas entradas. De ser posible M’ tendrá menos estados que M. 

Los estados inalcanzables son aquellos que no pueden alcanzarse desde el estado inicial, independientemente de los símbolos de entrada. Los estados inalcanzables pueden ser removidos. 

Los estados de M pueden ser particionados en clases de equivalencia tal que:

• Todos los estados de la misma clase tienen la misma salida. 

• La función de transición es tal que, para cada símbolo de entrada, todos los estados de la misma clase proceden a estados que están todos en la misma clase.

El problema de minimizar autómatas se reduce al problema de encontrar dichas clases de equivalencia. El problema se resuelve de manera iterativa, identificando lo que se conoce como clases de estados k-equivalentes. Dos estados s i y sj de M son kequivalentes si para todo α ∈ Σ*, tal que | α| ≤ k , fO ( s i, α) = fO ( sj , α).

 

l

l