Función de transición
para cadenas
Minimización
de AFD
Para cada AFD existe un
AFD con cantidad mínima de estados que acepta el mismo lenguaje.
El algoritmo de minimización
divide el conjunto de estados del AFD en clases de equivalencia. Los pasos
a seguir son los siguientes:
Construcción
del AFND a partir del AFND-
Dado un AFND-
es posible construir un AFND equivalente sin transiciones vacías
que reconoce el mismo lenguaje.
Los estados del nuevo autómata
son los estados importantes del AFND-
y el estado inicial del AFND-
.
Se denominan estados importantes aquellos estados a los que llega un arco
con un símbolo real como rótulo.
El estado inicial es el
estado inicial del AFND-.
La función de transición
se define teniendo en cuenta que existe una transición del estado
importante ei al estado importante ej con el símbolo
x, si existe algún estado ek tal que:
- se
puede llegar desde el estado ei al estado ek con
un camino de 0 ó mas transiciones ;
se permite ei = ek;
- en
el AFND- existe
una transición del estado ek al estado ej
rotulada con el símbolo x.
Los estados finales del
nuevo autómata son los estado finales del AFND-
y todos los estados ei del AFND-
para los cuales existe un camino con transiciones
,
en el AFND-
, a
algún estado final del AFND-
.
Autómata finito:
Modelo
Función de traducción
para cadenas