% this seems to work, just need to clean up the extra ()'s

function reg = dfsa2regexp(M)
% convert a DFSA to a regular expression
% see regexp2nfsa
%note! these aren't quite the same as matlab's regexps!
%here:
%      ()  is grouping
%      *   is Kleene star
%      +   is disjunction
%      @   is empty set

%this follows the construction in Lewis and Papadimitriou, pp 70-71

M = swap_dfsa_pq(M,M.q0,1);  % make sure the start state is 1

R = {};
n = length(M.Q);

%initialize:
for i=1:n
  for j=1:n
    reg = dqij(M,i,j);
    %reg = strrep(reg,'()*','@');    
    R{i,j,1} = reg;
    %if ((i==j)&~isempty(reg))
    if (i==j)
      if ~isempty(reg)
        reg = ['(@+' R{i,j,1} ')'];
	%reg = ['@+' R{i,j,1} ];
      else
	reg = '@';
      end
      %reg = strrep(reg,'(@+@)','@');
      %reg = strrep(reg,'+()','');
      R{i,j,1} = reg;
    end
  end
end

%induction:
for k=1:n
  for i=1:n
    for j=1:n
      % reg = ['(' R{i,j,k} '+' R{i,k,k} R{k,k,k} '*' R{k,j,k} ')'];
      % if any R(i,j,k) is empty then all of its concatenates are cancelled
      reg1 = '';
      if ~isempty(R{i,j,k})
	reg1 = R{i,j,k};
      end
      reg2 = '';
      if ((~isempty(R{i,k,k}))&(~isempty(R{k,k,k}))&(~isempty(R{k,j,k})))
	reg2 = [ R{i,k,k} R{k,k,k} '*' R{k,j,k} ];
      end
      reg = ['(' reg1 '+' reg2 ')'];      
      
      % make sure it's legal
      %reg = strrep(reg,'+*','+');
      reg = strrep(reg,'(+','(');
      reg = strrep(reg,'+)',')');
      reg = strrep(reg,'()','');
      
      % clean up a bit
      reg = clean_eps(reg);
      
      % minimize it
      reg = remove_redun(reg);
    
      R{i,j,k+1} = reg;
    end
  end
end

reg = '';
for j=1:n
  if ismember(j,M.F)
    reg = [reg '+' R{1,j,n+1}];
  end
end
reg=reg(2:end);
return


function reg = remove_redun(reg)
% reg is surrounded by ()
global ALF
nalf = ['@' ALF];
reg1 = reg(2:end-1);
if (mod(length(reg1),2)) % length is odd
  if (length(reg1)==1)
    reg = reg1;
  else
    mid = ceil(length(reg1)/2);
    if (reg1(mid)=='+')
      left = reg1(1:mid-1);
      rigt = reg1(mid+1:end);
      lu = unique(left);
      ru = unique(rigt);
      if (all(ismember(lu,nalf))&all(ismember(ru,nalf))&strcmp(lu,ru))
        if (length(lu)>1)
	  reg = ['(' lu ')'];
        else
	  reg = lu;
        end
      end
    end
  end
end
return

function reg = clean_eps(reg)
global ALF
nalf = ['@' ALF];
reg = strrep(reg,'@*','@');
x=find(reg=='@');
x(end+1)=length(reg)+1;
reg1 = reg(1:x(1)-1);
for i=1:length(x)-1
  j = x(i);
  cL = reg(j-1);
  cR = reg(j+1);
  if ~any(ismember([cL cR],nalf))
    % neither left nor right char is a letter
    % the @ is necessary
    reg1(end+1)='@';
  end
  reg1 = [reg1 reg(x(i)+1:x(i+1)-1)];
end
reg = reg1;
return


function reg = clean_paren(reg)
global ALF
nalf = ['@' ALF];
xL=find(reg=='(');
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%NOT FINISHED!!!!!!!!!!!!!!!!!
return




function u = dqij(M,i,j)
% S = { s\in \Sigma s.t. d(qi,s)=qj
S = '';
for s=M.ALF
  p = dfsa_delta(M,i,s);
  if (p==j)
    S(end+1)=s;
  end
end
if (length(S)>1)
  %u=['(' S ')'];
  u = SIG(S);
%elseif (length(S)==0)
%  u = '@';
else
  u = S;
end
%u = SIGSTAR(S);
%u = strrep(u,'()*','@'); %because () and @ mean different things!
return

function re = SIG(u)
k=length(u);
P=repmat('+',1,k);
up = [u;P];
up = up(:)';
re = ['(' up(1:end-1) ')'];
return


function re = SIGSTAR(u)
k=length(u);
P=repmat('+',1,k);
up = [u;P];
up = up(:)';
re = ['(' up(1:end-1) ')*'];
return