Logo Search packages:      
Sourcecode: lttoolbox version File versions  Download package

void Transducer::determinize ( int const   epsilon_tag = 0  ) 

Determinize the transducer

Parameters:
epsilon_tag the tag to take as epsilon

Definition at line 286 of file Transducer.C.

References clear(), closure(), finals, initial, isEmptyIntersection(), and transitions.

Referenced by minimize().

{
  vector<set<int> > R(2);
  map<int, set<int> > Q_prima;
  map<set<int>, int> Q_prima_inv;

  map<int, multimap<int, int> > transitions_prima;

  unsigned int talla_Q_prima = 0;
  Q_prima[0] = closure(initial, epsilon_tag);

  Q_prima_inv[Q_prima[0]] = 0;
  R[0].insert(0);

  int initial_prima = 0;
  set<int> finals_prima;

  if(finals.find(initial) != finals.end())
  {
    finals_prima.insert(0);
  }
 
  int t = 0;

  while(talla_Q_prima != Q_prima.size())
  {
    talla_Q_prima = Q_prima.size();
    R[(t+1)%2].clear();
    
    for(set<int>::iterator it = R[t].begin(), limit = R[t].end(); 
        it != limit; it++)
    {
      if(!isEmptyIntersection(Q_prima[*it], finals))
      {
      finals_prima.insert(*it);
      }

      map<int, set<int> > mymap;      

      for(set<int>::iterator it2 = Q_prima[*it].begin(), 
                             limit2 = Q_prima[*it].end();
        it2 != limit2; it2++)
      {
        for(multimap<int, int>::iterator it3 = transitions[*it2].begin(),
                                         limit3 = transitions[*it2].end();
          it3 != limit3; it3++)
      {
        if(it3->first != epsilon_tag)
        {
          set<int> c = closure(it3->second, epsilon_tag);
           
          for(set<int>::iterator it4 = c.begin(), limit4 = c.end(); 
              it4 != limit4; it4++)
          {
            mymap[it3->first].insert(*it4);
          }
        }
      }
      }

      // adding new states  
      for(map<int, set<int> >::iterator it2 = mymap.begin(), limit2 = mymap.end(); 
        it2 != limit2; it2++)
      {   
      if(Q_prima_inv.find(it2->second) == Q_prima_inv.end())
      {
        int etiq = Q_prima.size();
        Q_prima[etiq] = it2->second;
        Q_prima_inv[it2->second] = etiq;
        R[(t+1)%2].insert(Q_prima_inv[it2->second]);
          transitions_prima[etiq].clear();          
      }
        transitions_prima[*it].insert(pair<int, int>(it2->first, Q_prima_inv[it2->second]));
      }
    } 

    t = (t+1)%2;
  }

  transitions = transitions_prima;
  finals = finals_prima;
  initial = initial_prima;
}


Generated by  Doxygen 1.6.0   Back to index