function [S,STR]=dfsa2monoid_str(A,semigroup)
% computes the syntactic monoid S of DFSA A
% the elements of the monoid are strings [string equivalence classes]
% as opposed to abstract elements, indexed by the integers

% though this isn't built into the definition of a DFSA,
% we're going to assume that Q=1,2,...,n w/o gaps

if ~exist('semigroup','var')
  semigroup = 0;
  % a semigroup has no identity, unlike a monoid, which does!
end

G = {};
STR = {};
if ~semigroup
  % it's a monoid, include identity
  STR{end+1} = ''; %empty string corresponds to identity operator
  G{end+1} = id(A);
end
for s=A.ALF
  x = sig_action(A,s);
  gind = findG(G,x);
  if ~gind
    G{end+1} = x;
    STR{end+1} = s;
    % note: we're ignoring the (somewhat degenerate) case
    % where two letters have identical action on the states
  end
end

%now G consists of all the generators
%since we KNOW that the monoid is finite, 
%we can go ahead and apply the following "reckless" algorithm

S = [];
done = 0;
while ~done
  done = 1;
  for i=1:length(G)    
    for j=1:length(G)
      x = G{i};
      y = G{j};
      z = x*y;
      gind = findG(G,z);
      if ~gind
          done = 0;
          G{end+1}=z;
          S(i,j) = length(G);
          u = STR{i};
          v = STR{j};
          w = [u v];
          STR{end+1}=w;
      else
          S(i,j) = gind;
      end
    end
  end
end

return


function i = findG(G,z)
if isempty(G)
  i = 0;
  return
end
good = 0;
for i=1:length(G)
  if isequal(G{i}+0,z+0)  %doesn't work w/o unsparsing
    good = 1;
    break;
  end
end
i = i*good;
return


function x = id(A)
% the identity element of S(A)
x = speye(length(A.Q));
return


function x = sig_action(A,s)
% the action of the letter s on Q
n = length(A.Q);

x = sparse(n,n);

for q=1:n
  p = dfsa_delta(A,q,s);
  x(q,p) = 1;
end
return