youxianzidongjihuajian.txt

有限自动机的确定化及化简 1、更正了 DFA_simplify2 中的错误 2、增加新旧状态对照表 ds_temp --NFA转DFA -- 输入字符 -- 要求 id

  go   
    
  nfa_to_dfa   
    
  select   *   from   ds   
  select   *   from   dm   
  select   *   from   ns_ds   
    
  --自动机   002   
  delete   from   ct   
  insert   into   ct   values(1,'a')   
  insert   into   ct   values(2,'b')   
    
  delete   from   ns   
  insert   into   ns   values(0,'N')   
  insert   into   ns   values(1,'N')   
  insert   into   ns   values(2,'N')   
  insert   into   ns   values(3,'N')   
  insert   into   ns   values(4,'N')   
  insert   into   ns   values(5,'N')   
  insert   into   ns   values(6,'N')   
  insert   into   ns   values(7,'N')   
  insert   into   ns   values(8,'N')   
  insert   into   ns   values(9,'N')   
  insert   into   ns   values(10,'Y')   
    
  delete   from   nm   
  insert   into   nm   values(0,'',1)   
  insert   into   nm   values(0,'',7)   
  insert   into   nm   values(1,'',2)   
  insert   into   nm   values(1,'',4)   
  insert   into   nm   values(2,'a',3)   
  insert   into   nm   values(3,'',6)   
  insert   into   nm   values(4,'b',5)   
  insert   into   nm   values(5,'',6)   
  insert   into   nm   values(6,'',1)   
  insert   into   nm   values(6,'',7)   
  insert   into   nm   values(7,'a',8)   
  insert   into   nm   values(8,'b',9)   
  insert   into   nm   values(9,'b',10)   
  go   
    
  nfa_to_dfa   
    
  select   *   from   ct   
  select   *   from   ds   
  select   *   from   dm   
  select   *   from   ns_ds   
    
    
  问题点数：0、回复次数：7Top 
1 楼jyk1970（）回复于 2005-04-17 17:40:57 得分 0 
  
  -----------------------------------------------------------------------   
  --dfa化简之一：删除无法到达的状态   
  drop   procedure   dfa_simplify1   
  go   
  create   procedure   dfa_simplify1   
  as   
  begin   
  declare   @t1   table(id   int)   
  declare   @t2   table(id   int)   
  declare   @t3   table(id   int)   
    
  insert   into   @t1   values(0)   
  insert   into   @t3   
  select   id   from   @t1   
  while   1=1   
  begin   
  delete   from   @t2   
  insert   into   @t2   
  select   distinct   ds2_id   from   dm   where   ds1_id   in   (select   id   from   @t1)   
  if   not   exists(select   *   from   @t2   where   id   not   in   (select   id   from   @t3))   
  begin   
  break   
  end   
  delete   from   @t1   
  insert   into   @t1   
  select   id   from   @t2   where   id   not   in   (select   id   from   @t3)   
  insert   into   @t3   
  select   id   from   @t1   
  end   
  delete   from   ds   where   id   not   in   (select   id   from   @t3)   
  delete   from   dm   where   ds1_id   not   in   (select   id   from   @t3)   
  end   
  go   
    
  --测试   
  delete   from   ds   
  delete   from   dm   
  insert   into   ds   values(0,'N')   
  insert   into   ds   values(1,'N')   
  insert   into   ds   values(2,'N')   
  insert   into   ds   values(3,'N')   
  insert   into   ds   values(4,'N')   
  insert   into   ds   values(5,'N')   
  insert   into   ds   values(6,'N')   
  insert   into   ds   values(7,'N')   
  insert   into   ds   values(8,'N')   
  insert   into   dm   values(0,'a',1)   
  insert   into   dm   values(0,'b',5)   
  insert   into   dm   values(1,'a',2)   
  insert   into   dm   values(1,'b',7)   
  insert   into   dm   values(2,'a',2)   
  insert   into   dm   values(2,'b',5)   
  insert   into   dm   values(3,'a',5)   
  insert   into   dm   values(3,'b',7)   
  insert   into   dm   values(4,'a',5)   
  insert   into   dm   values(4,'b',6)   
  insert   into   dm   values(5,'a',3)   
  insert   into   dm   values(5,'b',1)   
  insert   into   dm   values(6,'a',8)   
  insert   into   dm   values(6,'b',0)   
  insert   into   dm   values(7,'a',0)   
  insert   into   dm   values(7,'b',1)   
  insert   into   dm   values(8,'a',3)   
  insert   into   dm   values(8,'b',6)   
    
  --化简   
  dfa_simplify1   
    
  --结果   
  select   *   from   ds   
  select   *   from   dm   
    
  --dfa化简之二：消除等价状态   
  drop   procedure   dfa_simplify2   
  go   
  create   procedure   dfa_simplify2   
  as   
  begin   
  declare   @count1   int,   @count2   int   
  declare   @ct_id   int,   @ct_id_max   int,   @ct_ch   char(1)   
  declare   @ds   table(id   int,   finished   char(1),   g1   int,   g2   int)   
    
  insert   into   @ds     
  select   id,   finished,   (select   top   1   id   from   ds   where   finished=a.finished   order   by   id),   -1   from   ds   a   
  while   1=1   
  begin   
  select   @count1=count(*)   from   (select   distinct   g1   from   @ds)   as   x   
  select   @ct_id=1,   @ct_id_max=max(id)   from   ct   
  while   @ct_id<=@ct_id_max   
  begin   
  select   @ct_ch=ch   from   ct   where   id=@ct_id   
  update   a   set   a.g2=c.g1     
  from   @ds   a,   dm   b,   @ds   c   
  where   a.id=b.ds1_id   and   b.ds2_id=c.id   and   b.ct_ch=@ct_ch   
  update   a   set   a.g1=(select   top   1   id   from   @ds   where   g1=a.g1   and   g2=a.g2   order   by   id),   a.g2=-1     
  from   @ds   a     
  where   a.g2<>-1   
  select   @ct_id=@ct_id+1   
  end   
  select   @count2=count(*)   from   (select   distinct   g1   from   @ds)   as   x   
    
  if   @count2=@count1   break   
  end   
  update   a   set   a.finished=''   from   @ds   a   where   a.id<>(select   top   1   id   from   @ds   where   g1=a.g1   order   by   id)   
  delete   from   ds_temp   
  insert   into   ds_temp     
  select   *   from   @ds   
  update   c   set   c.ds2_id=a.id   
  from   @ds   a,   @ds   b,   dm   c     
  where   a.finished<>''   and   b.finished=''   and   a.g1=b.g1   and   b.id=c.ds2_id   
    
  delete   from   dm   where   ds1_id   in   (select   id   from   @ds   where   finished='')   
  delete   from   ds   where   id   in   (select   id   from   @ds   where   finished='')   
  end   
  go   
    
  --测试   
  delete   from   ds   
  delete   from   dm   
  insert   into   ds   values(0,'N')   
  insert   into   ds   values(1,'N')   
  insert   into   ds   values(2,'N')   
  insert   into   ds   values(3,'N')   
  insert   into   ds   values(4,'Y')   
  insert   into   ds   values(5,'Y')   
  insert   into   ds   values(6,'Y')   
  insert   into   dm   values(0,'a',5)   
  insert   into   dm   values(0,'b',2)   
  insert   into   dm   values(1,'a',6)   
  insert   into   dm   values(1,'b',2)   
  insert   into   dm   values(2,'a',0)   
  insert   into   dm   values(2,'b',4)   
  insert   into   dm   values(3,'a',3)   
  insert   into   dm   values(3,'b',5)   
  insert   into   dm   values(4,'a',6)   
  insert   into   dm   values(4,'b',2)   
  insert   into   dm   values(5,'a',3)   
  insert   into   dm   values(5,'b',0)   
  insert   into   dm   values(6,'a',3)   
  insert   into   dm   values(6,'b',1)   
    
  --化简   
  dfa_simplify2   
    
  --结果   
  select   *   from   ds   
  select   *   from   dm   
    
  --新旧状态对照   
  select   id   old,   g1   new,   finished   from   ds_temp   order   by   g1Top
2 楼jyk1970（）回复于 2005-04-17 17:52:03 得分 0 
--测试2   
  delete   from   ct   
  insert   into   ct   values(1,'a')   
  insert   into   ct   values(2,'b')   
  insert   into   ct   values(3,'c')   
    
    
  delete   from   ds   
  insert   into   ds   values(0,'N')   
  insert   into   ds   values(1,'N')   
  insert   into   ds   values(2,'N')   
  insert   into   ds   values(3,'N')   
  insert   into   ds   values(4,'N')   
  insert   into   ds   values(5,'Y')   
    
  delete   from   dm   
  insert   into   dm   values(0,'a',1)   
  insert   into   dm   values(0,'b',3)   
  insert   into   dm   values(1,'a',2)   
  insert   into   dm   values(1,'b',3)   
  insert   into   dm   values(2,'a',2)   
  insert   into   dm   values(2,'c',5)   
  insert   into   dm   values(3,'a',4)   
  insert   into   dm   values(3,'b',1)   
  insert   into   dm   values(4,'a',4)   
  insert   into   dm   values(4,'c',5)   
    
  --化简   
  dfa_simplify2   
    
  --结果   
  select   *   from   ct   
  select   *   from   ds   
  select   *   from   dm   
    
  --新旧状态对照   
  select   id   old,   g1   new,   finished   from   ds_temp   order   by   g1Top
3 楼jyk1970（）回复于 2005-04-17 17:58:22 得分 0 
--测试2中化简后的ds表内容   
  0 N   
  1 N   
  2 N   
  5 Y   
  --测试2中化简后的dm表内容   
  0 a 1   
  0 b 1   
  1 a 2   
  1 b 1   
  2 a 2   
  2 c 5   
  --测试2中化简后的新旧状态对照   
  0 0 N   
  1 1 N   
  3 1     
  2 2 N   
  4 2     
  5 5 Y   
  Top