youxianzidongjihuajian.txt

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

有限自动机的确定化及化简
1、更正了   dfa_simplify2   中的错误   
  2、增加新旧状态对照表   ds_temp   
  -----------------------------------------------------------------------   
  --nfa转dfa   
    
  --   输入字符   
  --   要求   id   必须从   1   开始连续递增   
  drop   table   ct   
  go   
  create   table   ct   
  (   
  id   int   not   null,   
  ch   char(1)   not   null,   
  )   
  go   
    
  --   nfa   state   
  --   规定：初始状态的id等于0   
  drop   table   ns   
  go   
  create   table   ns   
  (   
  id   int   not   null,   
  finished   char(1)   not   null   --'Y'/'N'   
  )   
  go   
    
  --   不确定自动机状态转换表   
  drop   table   nm   
  go   
  create   table   nm   
  (   
  ns1_id   int   not   null,   
  ct_ch   char(1)   not   null,   
  ns2_id   int   not   null   
  )   
  go   
    
  --   dfa   state   
  --   规定：初始状态的id等于0   
  drop   table   ds   
  go   
  create   table   ds   
  (   
  id   int   not   null,   
  finished   char(1)   not   null   --'Y'/'N'   
  )   
  go   
    
  --   确定自动机状态转换表   
  drop   table   dm   
  go   
  create   table   dm   
  (   
  ds1_id   int   not   null,   
  ct_ch   char(1)   not   null,   
  ds2_id   int   not   null   
  )   
  go   
    
  --   nfa   与   dfa   的状态关系对照表   
  drop   table   ns_ds   
  go   
  create   table   ns_ds   
  (   
  ns_id   int   not   null,   
  ds_id   int   not   null,   
  )   
  go   
    
  --因为目前   table   类型变量不能作为   function   或   procedure   参数进行传递   
  --所以专门设置一个表进行集合参数的传递   
  drop   table   st   
  go   
  create   table   st   
  (   
  id   int   not   null   
  )   
  go   
    
  --dfa_simplify2的中间结果   
  drop   table   ds_temp   
  go   
  create   table   ds_temp   
  (   
  id   int   not   null,   
  finished   char(1)   not   null,   --'Y'/'N'   
  g1   int   not   null,   
  g2   int   not   null   
  )   
  go   
    
    
  drop   function   e_closure   
  go   
  create   function   e_closure()   
  returns   @r   table(id   int)   
  as   
  begin   
  declare   @ok   char(1)   
  declare   @t1   table(id   int)   
  declare   @t2   table(id   int)   
  declare   @t3   table(id   int)   
    
  set   @ok='N'   
  insert   into   @t3     
  select   distinct   id   from   st   
    
  while   @ok='N'   
  begin   
  delete   from   @t1   
  insert   into   @t1   
  select   id   from   @t3   
  delete   from   @t2   
  insert   into   @t2   
  select   distinct   ns2_id     
  from   nm     
  where   ct_ch=''     
  and   ns1_id   in   (select   id   from   @t1)   
  delete   from   @t3   
  insert   into   @t3   
  select   id   from   @t1   
  union     
  select   id   from   @t2   
    
  if   exists(select   *   from   @t3   where   id   not   in   (select   id   from   @r))   
  begin   
  insert   into   @r   
  select   id   from   @t3   
  where   id   not   in   (select   id   from   @r)   
  end   
  else   
  begin   
  set   @ok='Y'   
  end   
  end   
  return   
  end   
  go   
    
  drop   function   e_move   
  go   
  create   function   e_move(@a_ct_ch   char(1))   
  returns   @r   table(id   int)   
  as   
  begin   
  declare   @ok   char(1)   
  declare   @t1   table(id   int)   
    
  insert   into   @t1   
  select   id   from   dbo.e_closure()   
    
  insert   into   @r   
  select   distinct   ns2_id     
  from   nm   a,   @t1   b   
  where   a.ns1_id=b.id   and   (a.ct_ch=@a_ct_ch   or   a.ct_ch='')     
  and   ns2_id   not   in   (select   id   from   @r)   
    
  return   
  end   
  go   
    
  --确定化处理   
  --ds.finished=''   表示此状态没有处理过   
  drop   procedure   nfa_to_dfa   
  go   
  create   procedure   nfa_to_dfa   
  as   
  begin   
  declare   @ds_id   int,   @ds_id_max   int,   @i   int,   @count1   int,   @count2   int,   @count3   int,   @ds_id_next   int   
  declare   @ct_id   int,   @ct_id_max   int,   @ct_ch   char(1)   
  declare   @st   table(id   int)   
    
  delete   from   ns_ds   
  delete   from   ds   
  delete   from   dm   
  delete   from   st   
  insert   into   st     
  select   id   from   ns   where   id=0   
  insert   into   ds   
  select   isnull(max(id)+1,0),   ''   from   ds   
  insert   into   ns_ds   
  select   id,   0   from   dbo.e_closure()   
    
  select   @ct_id_max=max(id)   from   ct   
  while   exists(select   *   from   ds   where   finished='')   
  begin   
  select   top   1   @ds_id=id   from   ds   where   finished=''   order   by   id   
  select   @ct_id=1   
  while   @ct_id<=@ct_id_max   
  begin   
  delete   from   st   
  insert   into   st   
  select   ns_id   from   ns_ds   where   ds_id=@ds_id   
    
  select   @ct_ch=ch   from   ct   where   id=@ct_id   
  delete   from   @st   
  insert   into   @st   
  select   id   from   dbo.e_move(@ct_ch)   
  delete   from   st   
  insert   into   st   
  select   id   from   @st   
  delete   from   @st   
  insert   into   @st   
  select   id   from   dbo.e_closure()   
    
  create   table   #t1(sn   int   identity(1,1),   id   int)   
  insert   into   #t1   select   id   from   @st   order   by   id   
  select   @count1=count(*)   from   #t1   
  select   @i=0,   @ds_id_max=max(id)   from   ds   
  while   @i<=@ds_id_max   
  begin   
  create   table   #t2(sn   int   identity(1,1),   id   int)   
  insert   into   #t2   select   ns_id   from   ns_ds   where   ds_id=@i   order   by   ns_id   
  select   @count2=count(*)   from   #t2   
  select   @count3=count(*)   from   #t1,   #t2   where   #t1.sn=#t2.sn   and   #t1.id=#t2.id   
  drop   table   #t2   
  if   @count1=@count3   and   @count2=@count3   
  begin   
  break   
  end   
  select   @i=@i+1   
  end   
  drop   table   #t1   
    
  if   @i>@ds_id_max   
  begin   
  select   @ds_id_next=@ds_id_max+1   
  insert   into   ds   values(@ds_id_next,   '')   
  insert   into   ns_ds   
  select   id,   @ds_id_next   from   @st   
  end   
  else   
  begin   
  select   @ds_id_next=@i   
  end   
  insert   into   dm   values(@ds_id,   @ct_ch,   @ds_id_next)   
    
  select   @ct_id=@ct_id+1   
  end   
    
  if   exists(select   *   from   ns_ds   where   ds_id=@ds_id   and   ns_id   in   (select   id   from   ns   where   finished='Y'))   
  begin   
  update   ds   set   finished='Y'   where   id=@ds_id   
  end   
  else   
  begin   
  update   ds   set   finished='N'   where   id=@ds_id   
  end   
  end   
  end   
  go   
    
  --自动机   001   
  insert   into   ct   values(1,'a')   
  insert   into   ct   values(2,'b')   
  insert   into   ns   values(0,'Y')   
  insert   into   ns   values(1,'N')   
  insert   into   nm   values(0,'a',0)   
  insert   into   nm   values(0,'a',1)   
  insert   into   nm   values(0,'b',1)   
  insert   into   nm   values(1,'a',0)