Construcción de subconjuntos: algoritmo

1 q’0 := ?-clausura(q0);

2 desmarcar(q’0);

3 estadosDFA := {q’0};

4 while (? T ? estadosDFA | not marcado(T)) do

5 begin

6 marcar(T);

7 for (cada símbolo de entrada, a) do

8 begin

9 H := ?-clausura(move(T, a));

10 if H ? estadosDFA then

11 begin

12 desmarcar(H);

13 estadosDFA := estadosDFA ? H

14 end

15 tranDFA[T, a] := H;

16 end

17 end

Dado un conjunto de estados S

de un NFA y un símbolo de entrada

a, definimos la operación move(S, a),

como el conjunto de todos los estados

que pueden alcanzarse desde un estado

de S mediante una transición con

el símbolo de entrada, a

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica