function [b,str] = accept_str(M)
% returns [1,str] if M accepts some string str
% and [0,''] otherwise

% this is simple to resolve:
% is there a path from M.q0 to one of M.F?

nQ = length(M.Q);
% we only need to consider paths of length nQ

t = 1; b = 1;
Q{1} = M.q0;
while ((t<=nQ) & b)
  if ~isempty(intersect(Q{t},M.F))
    % we've reached a final state
    b = 0;
  else
    Q{t+1} = [];
    for q=Q{t}
      %for s=double(M.ALF)
      for s=M.ALF
	r = dfsa_delta(M,q,s);
	Q{t+1}(end+1) = r;
      end
    end
    Q{t+1} = unique(Q{t+1});
    t = t + 1;
  end
end

b=~b;
str = '';

%keyboard

if b
  % trace a path back from Q{}
  QF = intersect(Q{end},M.F);
  q = QF(1);
  for t=length(Q):-1:2
    %[q,s] = get_parent(M,q);
    [q,s] = get_parent(M,q,Q{t-1});
    str = [s,str];
  end
end

return


%function [q0,s0] = get_parent(M,q1);
% returns SOME [q0,s0] s.t. delta(q0,s0)=q1
function [q0,s0] = get_parent(M,q1,cand);
% returns SOME [q0,s0] from among cand s.t. delta(q0,s0)=q1

good = 0;
qn = 1;
%while ((qn<=length(M.Q)&~good))
while ((qn<=length(cand)&~good))
  %q = M.Q(qn);
  q = cand(qn);
  sn = 1;
  while ((sn<=length(M.ALF)&~good))
    %s = double(M.ALF(sn));
    s = M.ALF(sn);
    good = (q1 == dfsa_delta(M,q,s));
    if good
      q0 = q;
      s0 = s;
    end
    sn = sn + 1;
  end
  qn = qn + 1;
end

if ~good
  %keyboard
  error('state has no parent!!') %this should not happen
end
return