Minimizacion de estados en un AF

La minimizacion es un proceso que nos permite encontrar, para un dadi automaa finito M, un automata 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.

Si esto no es posible, entonces M ya es un autómata mínimo.

Estads Inalcanzables

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

Estados Equivalentes

Dos estados si y sj de M son equivañentes si para toda denot el conjunto de cadenas de longitud finita sobre el alfabeto de entrada.

de esta manera, estados equivalentes producen salidas equivalentes para una cadena de entrada dada.