function str = dfsa_randgen(M,stopprob)
% randomly generate a string accepted by DFSA M

if empty_fsa(M)
  error('The fsa accepts no strings!')
end

if ~exist('stopprob','var')
  stopprob = 0.5;
end

str = '';
q = M.q0;
DS = deadstates_fsa(M);
done = 0;
nalf = length(M.ALF);
global unif_disc_pdf_N  % the cardinality of the support se
unif_disc_pdf_N = nalf;


while ~done
  ai = sample_discr(@unif_disc_pdf,1);
  s = M.ALF(ai);
  q1 = dfsa_delta(M,q,s);
  if ismember(q1,DS)
    if ismember(q1,M.F)
      str = [str,s];
      done = 1;
    end
    % never mind this draw -- it leads to a dead state
    continue
  end
  str = [str,s];
  if ismember(q1,M.F)
    % flip a coin -- are we done?
    done = (rand<stopprob);
    [qq2,ss1] = get_ddelta(M,q1);
    if all(ismember(qq2,DS))
      % all children are dead states
      done = 1;
    end
  end
  q = q1;
end
  
return