3.2 - Conversión de un Autómata Finito No Determinista (AFND) a Autómata Finito Determinista (AFD).

Todo AFND estricto, puede ser transformado a AFD utilizando un algoritmo que transforma los estados del AFND en nuevos estados que son subconjuntos de los estados originales y aplica a los mismos la clausura para confirmar la conexidad entre cada uno de los componentes y así eliminar el indeterminismo.

Sea un autómata finito estrictamente no determinista (AFND) definido por la 5-tupla A=<Q, T, g, F, q₀>, donde Q es el conjunto de estados, T el alfabeto de símbolos terminales, la relación de transiciones 

1.    A se transforma en A_AFD=<Q_A,T, g_A,F_A,q_0A>', tal que:

a.    V_A=P(V)-{{}}, con P(V) que es el conjunto potencia de los vértices de A.

b.    F_A={x | }.

c.    g_A={<r,x,q> | }.

d.    q_0A={q₀}

2.    Luego se eliminan de A_AFD todos los estados y sus correspondientes transiciones inalcanzables desde el estado inicial q_0A.

Ejemplo

Véase el proceso de transformación de AFND a AFD del autómata A=<{q0,q1,f},{a,b},{<q0,a,q0>,<q0,b,q0>,<q0,a,q1>,<q1,b,f>},{f},q0>, que reconoce a las cadenas de as y bs que comienzan con cualquiera cantidad de estas letras y terminan forzosamente en ab. 

Primero se obtiene autómata derivado A_AFD=<V_AFD,T_AFD,g_AFD,F_AFD,{q0}> a partir del conjunto potencia de los estados de A donde:

·         V_AFD={{q0},{q1},{f},{q0,q1},{q0,f},{q1,f}, {q0,q1,f}}.

·         T_AFD={a,b}.

·         F_AFD={{f},{q0,f},{q1,f}, {q0,q1,f}}.

Luego se retiran los estados inaccesibles {q1}, {f}, {q1,f}, {q0,q1,f}, determinados mediante la clausura de {q0}, y queda:

·         A_AFD={{q0,{q0,q1},{q0,f}},{a,b},{<{q0},b,{q0}>,<{q0},a,{q0,q1}>,<{q0,q1},a,{q0,q1}>,<{q0,q1},b,{q0,f}>,<{q0,f},a,{q0,q1}>,<{q0,f},b,{q0}>},{ {q0,f} },{q0}}.