function DFSA = n2dfsa(NFSA)
% convets a NFSA to equivalent DFSA (non-trivial)
% see str2nfsa.m for basic nfsa definitions

%this follows the construction in Lewis and Papadimitriou, pp 60-62

global AUX1  % auxiliary array to speed up computation
AUX1 = 2.^(length(NFSA.Q)-1:-1:0);


DFSA.ALF = setdiff(NFSA.ALF,'@'); %dont need the @ char

EG=build_EG(NFSA);
E = find(EG(NFSA.q0,:));
DFSA.q0 = set2state(E,NFSA.Q);


% the power set of Q:
POWSET = list_all_ind(repmat([2],[length(NFSA.Q) 1]))-1;
DSTATS = 1:2^length(NFSA.Q);
DFSA.F = [];
for qf = NFSA.F
  inds = find(POWSET(:,qf));
  DFSA.F=[DFSA.F,inds'];
  %for i=inds'
  %  %DFSA.F(end+1) = arr2state(POWSET(i,:));
  %  DFSA.F(end+1) = DSTATS(i);
  %end
end
DFSA.F = unique(DFSA.F);

DFSA.Q = DSTATS;
DFSA = init_ddelta(DFSA);
PROGstart(length(DSTATS),'determinizing...');
for Qi=DSTATS
  for s=DFSA.ALF
    Q = find(POWSET(Qi,:));
    %q1 = set2state(Q,NFSA.Q);
    q1 = Qi;
    DQS = [];
    for q=Q
      P = nfsa_delta(NFSA,q,s);
      for p=P
        E = find(EG(p,:));	
	DQS = union(DQS,E);
      end
    end
    q2 = set2state(DQS,NFSA.Q);
    DFSA = set_ddelta(DFSA,q1,s,q2);
  end
  PROGupdate(Qi);
end
PROGend;

DFSA = remove_unreachable(DFSA);
return


function EG=build_EG(NFSA)
% builds a digraph of all states reachable from each other
% w/o reading input

n = length(NFSA.Q);
Id = eye(n);
EG = zeros(length(NFSA.Q));

for q1=NFSA.Q
  R = nfsa_delta(NFSA,q1,'@');
  EG(q1,R) = 1;
end

EG = (Id+EG)^(n-1);

return



function R = E(q)
% R is all states reachable from q w/o reading input
return



function q = set2state(V,Q)
x = ismember(Q,V);
q = arr2state(x);
return

function q = arr2state(x)
global AUX1
q = AUX1*x'+1;
return


function q = arr2state_slow(x)
y = num2str(x);
y = strrep(y,' ','');
q = bin2dec(y)+1;
return