function b = run_nfsa(NFSA,str)
%function [b,B] = run_nfsa(NFSA,str)
% B is the acceptance status of the string during the run

% does the given NFSA accept str?
% see str2nfsa.m for basic nfsa definitions

% this is tricky because of epsilon-transitions
% which allow potentially infinite loops
% we take care of this by keeping track of a "state of the world"
% WRLD(:,1) = position of automaton head on str (already read)
% WRLD(:,2) = current state of automaton

global WRLD

%B = [];

TQ = [0 NFSA.q0];
WRLD = TQ;
while ~isempty(TQ);
  TQ = advance_head(NFSA,TQ,str);
end

% now deciding acceptance is easy:
x=find(WRLD(:,1)==length(str));
y=WRLD(x,2);
b=any(ismember(y,NFSA.F));
return


function TQ1 = advance_head(NFSA,TQ,str)
global WRLD
TQ1=[];
for j=1:size(TQ,1)
  t = TQ(j,1); q = TQ(j,2);
  % all the states from epsilon-transitions:
  Re = nfsa_delta(NFSA,q,'@');
  TQe = update_world(Re,t);
  % all the states from other transitions:
  TQs = [];
  if (t<length(str))
    t = t+1;
    s = str(t);
    Rs = nfsa_delta(NFSA,q,s);
    TQs = update_world(Rs,t);
  end
  TQ1 = [TQ1;TQe];
  TQ1 = [TQ1;TQs];  
end
return



function TQ = update_world(R,t)
global WRLD
TQ = [];
for r=R
  if newstate(t,r) 		% haven't been in this state yet
    WRLD = [WRLD;[t r]];
    TQ = [TQ;[t r]];
  end
end
return


function b = newstate(t,r)
% have we been here before?
global WRLD
x=find(WRLD(:,1)==t);
y=WRLD(x,2);
x=find(y==r);
b=isempty(x);
return