本源码可以用来对确定化的有限自动机进行化简

用某高级语言写出DFA最小化的程序，这是一道作业题。   
  由于DFA最小化的算法众所周知，所以本题的关键是如何定义高效的数据结构来实现算法。   
  下面是我的解答，但我总觉得这个程序不够漂亮，希望大家能帮助改进或提供更好的答案。不胜感激。   
    
  解：   
    DFA=(t,S,f,S0,E)   
    其中t是字母表，   
    S是非空有穷状态集，   
    f是Sxt->S的映射，   
    S0是唯一的开始状态，   
    E是非空终止状态集合。   
    
  算法说明：   
  1.   将DFA中所有状态初始化分为终止状态1(state[i]=1)和非终止状态0(state[i]=0)两个集合   
  2.   将这两个状态入队，重复3-4，直到队列长度不再增长为止   
        (事实上，在实现时，并不是真的要显示地使用这样的队列)   
  3.   取出队头元素，依照算法划分为若干新的状态集合，   
  4.   将这些集合依次插入队尾。   
  5.   取每个状态集的代表元素，确定新的状态。实现dfa最小化.   
    
  函数divede(i)的作用是:   
      将状态集i分为两部分   
      1:   与状态集i的第一个元素     同后继的所有元素组成的集合，仍保留在状态集i中   
      2:   ~~~~~~~~~~~~~~~~~~~~~不同~~~~~~~~~~~~~~~~~~~~~~~~，保存在新状态集newstate中   
      divide:=true       :划分成功   
      divide:=false     :划分不成功(i当前不可再分)   
      由此可得，以下代码：     
              while   divide(i)   do                     
              begin   
                  i:=newstate;   
                  newstate:=newstate+1;   
              end;   
      的作用为将状态集i划分到当前不可再分   
    
  数据结构说明:   
  const   
      maxsize=....;     //DFA的最多状态数   
      m=....;                 //DFA字符集所含字符个数     
  TYPE   
      FUNC=array[0..maxsize-1,0..m-1]   of   0..maxsize-1;   
      TS=array[0..maxsize-1]   of   0..maxsize-1;   
    
      DFA=record   
                  f:FUNC;                 //   f[i,j]=k表示状态Si在tj的输入下的后继为状态Sk   
                  S:TS;                     //   S[i]=0:   Si为非终止状态;   S[i]=1:   Si为终止状态   
                  n:1..maxsize;     //   此DFA的总状态数   
              end;   
    
  算法实现:   
  procedure   minimize(dfa1:DFA;   VAR   dfa2:DFA);   
  var   
      state:TS;             //state[i]=j   表示dfa1中状态Si当前正属于状态集j中;   
      count,newstate:integer;   
  begin   
      for   i:=0   to   dfa1.n   do     
          state[i]:=dfa1.S[i];     //初始化state为两个状态集:终止和非终止   
        
      //newstate表示下一个将要产生的状态号,同时也代表当前总状态数   
      newstate:=2;     
    
  //划分状态集合：   
      count:=0;   
      while   count<newstate   do                           //当不再有新的划分时循环结束   
      begin   
          count:=newstate;   
          for   i:=0   to   newstete-1   do   
          begin   
              j:=i;                                                       //j:=delQ(Q);     
              while   divide(j)   do                             //将状态集划分   
              begin   
                  j:=newstate;   
                  newstate:=newstate+1;   
              end;   
          end;//for   
      end;//while   
    
  //取每个集合的代表元素，生成新DFA:   
      for   i:=0   to   newstate-1   do   
      begin   
          j:=0;   
          while   state[j]<>i   do   j:=j-1;     //找到状态集i的第一个元素Sj   
          for   t:=0   to   m-1   do                         //生成DFA2.f的一行     
              DFA2.f[i,t]:=state[DFA1.f[j,t]];   
          DFA2.S[i]:=DFA1.S[j];                   //生成DFA2.S           
      end;   
      DFA2.S0:=state[DFA1.s0];                   
      DFA2.n:=newstate;   
  end;   
    
    
  其中divide为minimize的内部函数，定义如下:   
  function   divide(i:0..maxsize-1):boolean;   
  begin   
      j:=0;   
      while   state[j]<>i   do             //找到状态集i的第一个元素Sj(代表元素)   
          j:=j+1;                                 
      k:=j;                                           //保留此状态   
      j:=j+1;                                       //j继续作为循环变量   
      while   j<maxsize   do   
      begin   
          t:=0       equal:=true;   
          while   (t<m-1)   and   equal   do       //Sj与Sk同后继？   
              if   state[DFA1.f[j,t]]<>state[DFA1.f[k,t]]   then       
                  equal:=false   
              else   
                  t:=t+1;   
          if   not   equal   then             //Sj与Sk不同后继则Sj并入新集合     
          begin   
              state[j]:=newstate;   
              divide:=false;                 
          end;   
      end;   
  end;