cfl_regular.cpp
Go to the documentation of this file.
1 /** @file cfl_regular.cpp
2 
3 Operations on regular languages.
4 See [Cassandras and Lafortune. Introduction to Discrete Event Systems] for an
5 introduction to regular language operations.
6 Operations are always performed on language(s) marked by the passed generator(s),
7 resulting in the language(s) marked by the resulting generator(s).
8 Only if mentioned extra, the same is done for the involved generated (prefix-closed)
9 languages.
10 
11 */
12 
13 /* FAU Discrete Event Systems Library (libfaudes)
14 
15 Copyright (C) 2006 Bernd Opitz
16 Copyright (C) 2008 Sebstian Perk
17 Exclusive copyright is granted to Klaus Schmidt
18 
19 This library is free software; you can redistribute it and/or
20 modify it under the terms of the GNU Lesser General Public
21 License as published by the Free Software Foundation; either
22 version 2.1 of the License, or (at your option) any later version.
23 
24 This library is distributed in the hope that it will be useful,
25 but WITHOUT ANY WARRANTY; without even the implied warranty of
26 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 Lesser General Public License for more details.
28 
29 You should have received a copy of the GNU Lesser General Public
30 License along with this library; if not, write to the Free Software
31 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
32 
33 
34 #include "cfl_regular.h"
35 #include "cfl_determin.h"
36 
37 
38 /* turn on debugging for this file */
39 //#undef FD_DF
40 //#define FD_DF(a) FD_WARN(a);
41 
42 namespace faudes {
43 
44 // LanguageUnionNonDet(rGen1, rGen2, rResGen)
45 void LanguageUnionNonDet(const Generator& rGen1, const Generator& rGen2,
46  Generator& rResGen) {
47 
48  FD_DF("LanguageUnionNonDet("<< rGen1.Name()
49  << "," << rGen2.Name() << ")");
50 
51  // are state names enabled?
52  bool stateNamesEnabled=rResGen.StateNamesEnabled();
53 
54  // use pointer pResGen to result rResGen; if rResGen is identical to
55  // one of the parameters, allocate temporary object and copy back later
56  Generator* pResGen = &rResGen;
57  if(&rResGen== &rGen1 || &rResGen== &rGen2) {
58  pResGen= rResGen.New();
59  }
60 
61  // prepare result
62  pResGen->Clear();
63 
64  // union of alphabets
65  pResGen->InjectAlphabet(rGen1.Alphabet()+rGen2.Alphabet());
66 
67  // Maps from states of rGen1 and rGen2 to states of ResGen
68  std::map<Idx,Idx> Gen1StatesMap;
69  std::map<Idx,Idx> Gen2StatesMap;
70 
71  // "union" of states: insert states representing the states of rGen1 and rGen2
72  StateSet::Iterator sit;
73  for (sit = rGen1.StatesBegin(); sit != rGen1.StatesEnd(); ++sit) {
74  if (stateNamesEnabled) {
75  Gen1StatesMap[*sit] = pResGen->InsState(pResGen->UniqueStateName(rGen1.StateName(*sit)+"(1)"));
76  }
77  else {
78  Gen1StatesMap[*sit] = pResGen->InsState();
79  }
80  }
81  for (sit = rGen2.StatesBegin(); sit != rGen2.StatesEnd(); ++sit) {
82  if (stateNamesEnabled) {
83  Gen2StatesMap[*sit] = pResGen->InsState(pResGen->UniqueStateName(rGen2.StateName(*sit)+"(2)"));
84  }
85  else {
86  Gen2StatesMap[*sit] = pResGen->InsState();
87  }
88  }
89 
90  // "union" of transition relations
92  for (tit = rGen1.TransRelBegin(); tit != rGen1.TransRelEnd(); ++tit) {
93  pResGen->SetTransition(Gen1StatesMap[tit->X1], tit->Ev, Gen1StatesMap[tit->X2]);
94  }
95  for (tit = rGen2.TransRelBegin(); tit != rGen2.TransRelEnd(); ++tit) {
96  pResGen->SetTransition(Gen2StatesMap[tit->X1], tit->Ev, Gen2StatesMap[tit->X2]);
97  }
98 
99  // "union" of init states
100  for (sit = rGen1.InitStatesBegin(); sit != rGen1.InitStatesEnd(); ++sit) {
101  pResGen->SetInitState(Gen1StatesMap[*sit]);
102  }
103  for (sit = rGen2.InitStatesBegin(); sit != rGen2.InitStatesEnd(); ++sit) {
104  pResGen->SetInitState(Gen2StatesMap[*sit]);
105  }
106 
107  // "union" of marked states
108  for (sit = rGen1.MarkedStatesBegin(); sit != rGen1.MarkedStatesEnd(); ++sit) {
109  pResGen->SetMarkedState(Gen1StatesMap[*sit]);
110  }
111  for (sit = rGen2.MarkedStatesBegin(); sit != rGen2.MarkedStatesEnd(); ++sit) {
112  pResGen->SetMarkedState(Gen2StatesMap[*sit]);
113  }
114 
115  // set name of result
116  pResGen->Name(CollapsString("UnionNonDet("+rGen1.Name()+","+rGen2.Name()+")"));
117 
118  // if necessary, move pResGen to rResGen
119  if(pResGen != &rResGen) {
120  pResGen->Move(rResGen);
121  delete pResGen;
122  }
123 
124 }
125 
126 // LanguageUnion(rGen1, rGen2, rResGen)
127 void LanguageUnion(const Generator& rGen1, const Generator& rGen2,
128  Generator& rResGen) {
129 
130  FD_DF("LanguageUnion("<< rGen1.Name()
131  << "," << rGen2.Name() << ")");
132 
133  // fix name
134  std::string name1 = rGen1.Name();
135  std::string name2 = rGen2.Name();
136 
137  // avoid copy
138  Generator* pTempGen = rResGen.New();
139 
140  // perform nondeterministic language union
141  LanguageUnionNonDet(rGen1, rGen2, *pTempGen);
142 
143  // make deterministic
144  Deterministic(*pTempGen, rResGen);
145 
146  // dispose temp
147  delete pTempGen;
148 
149  // set name of result
150  rResGen.Name(CollapsString("Union("+name1+","+name2+")"));
151 
152 }
153 
154 // LanguageUnion(rGenVec, rResGen)
155 void LanguageUnion(const GeneratorVector& rGenVec, Generator& rResGen) {
156 
157  // ignore empty
158  if(rGenVec.Size()==0) {
159  return;
160  }
161 
162  // copy one
163  if(rGenVec.Size()==1) {
164  rResGen=rGenVec.At(0);
165  return;
166  }
167 
168  // avoid final copy
169  Generator* pTempGen = rResGen.New();
170 
171  // run union on others
172  LanguageUnionNonDet(rGenVec.At(0),rGenVec.At(1),*pTempGen);
173  for(GeneratorVector::Position i=2; i<rGenVec.Size(); i++)
174  LanguageUnionNonDet(rGenVec.At(i),*pTempGen,*pTempGen);
175 
176  // make deterministic
177  Deterministic(*pTempGen, rResGen);
178 
179  // dispose temp
180  delete pTempGen;
181 
182  // set name of result
183  rResGen.Name(CollapsString("Union(...)"));
184 }
185 
186 
187 // LanguageIntersection(rGen1, rGen2, rResGen)
188 void LanguageIntersection(const Generator& rGen1, const Generator& rGen2,
189  Generator& rResGen) {
190  FD_DF("LanguageIntersection("<< rGen1.Name() << "," << rGen2.Name() << ")");
191 
192  // fix name
193  std::string name1 = rGen1.Name();
194  std::string name2 = rGen2.Name();
195 
196  // the product of rGen1 and rGen2 implements the language intersection
197  Product(rGen1, rGen2, rResGen);
198  rResGen.Name(CollapsString("Intersection("+name1+","+name2+")"));
199  FD_DF("LanguageIntersection("<< rGen1.Name() << "," << rGen2.Name() << "): done");
200 
201 }
202 
203 
204 // LanguageIntersection(rGenVec, rResGen)
205 void LanguageIntersection(const GeneratorVector& rGenVec, Generator& rResGen)
206 {
207 
208  // ignore empty
209  if(rGenVec.Size()==0) {
210  return;
211  }
212 
213  // copy one
214  if(rGenVec.Size()==1) {
215  rResGen=rGenVec.At(0);
216  return;
217  }
218 
219  // run product on others
220  LanguageIntersection(rGenVec.At(0),rGenVec.At(1),rResGen);
221  for(GeneratorVector::Position i=2; i<rGenVec.Size(); i++)
222  LanguageIntersection(rGenVec.At(i),rResGen,rResGen);
223 }
224 
225 
226 // EmptyLanguageIntersection(rGen1, rGen2)
227 bool EmptyLanguageIntersection(const Generator& rGen1, const Generator& rGen2) {
228  FD_DF("EmptyLanguageIntersection("<< rGen1.Name()
229  << "," << rGen2.Name() << ")");
230 
231  // not tested for non-det automata
232  bool g1_det = rGen1.IsDeterministic();
233  bool g2_det = rGen2.IsDeterministic();
234  if( (!g1_det) || (!g2_det)) {
235  std::stringstream errstr;
236  errstr << "EmptyLanguageIntersection has not been tested for nondeterministic generators";
237  throw Exception("EmptyLanguageIntersection", errstr.str(), 201);
238  }
239 
240  // Perform product and break when a marking is reached simultaneously)
241 
242  // todo stack
243  std::stack< std::pair<Idx,Idx> > todo;
244  std::set< std::pair<Idx,Idx> > done;
245  // iterate variables
246  std::pair<Idx,Idx> currentstates, newstates;
247  StateSet::Iterator lit1, lit2;
248  TransSet::Iterator tit1, tit1_end, tit2, tit2_end;
249  // convenience
250  const StateSet& mark1 = rGen1.MarkedStates();
251  const StateSet& mark2 = rGen2.MarkedStates();
252  // restrict search to coaccessible states
253  StateSet coac1 = rGen1.CoaccessibleSet();
254  StateSet coac2 = rGen2.CoaccessibleSet();
255 
256  // push all combinations of coaccessible initial states on todo stack
257  FD_DF("EmptyLanguageIntersection: push all combinations of initial states to todo:");
258  StateSet init1 = coac1 * rGen1.InitStates();
259  StateSet init2 = coac2 * rGen2.InitStates();
260  for (lit1 = init1.Begin(); lit1 != init1.End(); ++lit1) {
261  for (lit2 = init2.Begin(); lit2 != init2.End(); ++lit2) {
262  currentstates = std::make_pair(*lit1, *lit2);
263  todo.push(currentstates);
264  }
265  }
266 
267  // process todo stack
268  bool empty = true;
269  FD_DF("EmptyLanguageIntersection: processing reachable states:");
270  while (!todo.empty()) {
271  // allow for user interrupt
272  // LoopCallback();
273  // allow for user interrupt, incl progress report
274  FD_WPC(done.size(),done.size()+todo.size(),"Product(): processing");
275  // get next reachable state from todo stack
276  currentstates = todo.top();
277  todo.pop();
278  done.insert(currentstates);
279  //FD_DF("EmptyLanguageIntersection: processing " << currentstates.first << "|" << currentstates.second);
280  // test for sync acceptance (do this here to include initial states)
281  if(mark1.Exists(currentstates.first) && mark2.Exists(currentstates.second)) {
282  empty=false;
283  break;
284  }
285  // iterate over all rGen1/rGen2 transitions
286  tit1 = rGen1.TransRelBegin(currentstates.first);
287  tit1_end = rGen1.TransRelEnd(currentstates.first);
288  tit2 = rGen2.TransRelBegin(currentstates.second);
289  tit2_end = rGen2.TransRelEnd(currentstates.second);
290  while((tit1 != tit1_end) && (tit2 != tit2_end)) {
291  // shared event
292  if(tit1->Ev == tit2->Ev) {
293  // push new state
294  newstates = std::make_pair(tit1->X2, tit2->X2);
295  if(done.find(newstates)==done.end())
296  if(coac1.Exists(newstates.first))
297  if(coac2.Exists(newstates.second))
298  todo.push(newstates);
299  // increment transition
300  ++tit1;
301  ++tit2;
302  }
303  // try resync tit1
304  else if (tit1->Ev < tit2->Ev) {
305  ++tit1;
306  }
307  // try resync tit2
308  else if (tit1->Ev > tit2->Ev) {
309  ++tit2;
310  }
311  }
312  }
313 
314 #ifdef FAUDES_CODE
315  // Alternative test for validation
316  Generator ProductGen;
317  ProductGen.StateNamesEnabled(false);
318  Product(rGen1, rGen2, ProductGen);
319  bool altempty = IsEmptyLanguage(ProductGen);
320  if(empty != altempty) {
321  rGen1.Write();
322  rGen2.Write();
323  FD_ERR("EmptyLanguageIntersection(): ERROR -- ref result: " << altempty);
324  }
325 #endif
326 
327  // done
328  return empty;
329 }
330 
331 // LanguageDisjoint(rGen1, rGen2)
332 bool LanguageDisjoint(const Generator& rGen1, const Generator& rGen2) {
333  FD_DF("LanguageDisjoint("<< rGen1.Name()
334  << "," << rGen2.Name() << ")");
335  return EmptyLanguageIntersection(rGen1,rGen2);
336 }
337 
338 // Automaton(rGen)
339 Idx Automaton(Generator& rGen, const EventSet& rAlphabet) {
340  FD_DF("Automaton("<< rGen.Name() << "," << rAlphabet.Name() << ")");
341 
342  TransSet::Iterator tit;
343  EventSet::Iterator eit;
344  StateSet::Iterator sit;
345 
346  // for correct result, rGen has to be deterministic!
347 #ifdef FAUDES_CHECKED
348  if ( !(rGen.IsDeterministic()) ) {
349  FD_WARN("Automaton(): nondeterministic parameter " << rGen.Name() <<".");
350  }
351 #endif
352 
353  // prepare result
354  rGen.Name(CollapsString("Automaton(" + rGen.Name() + "," + rAlphabet.Name() + ")"));
355 
356  // extend rGen.Alphabet() by rAlphabet
357  rGen.InjectAlphabet(rGen.Alphabet()+rAlphabet);
358 
359  // we used to trim ... but this will fail for omega automata
360  // rGen.Trim();
361 
362  // introduce a dump state (unmarked)
363  Idx dump;
364  if (rGen.StateNamesEnabled()) {
365  std::string dumpstr=rGen.UniqueStateName("dump");
366  dump = rGen.InsState(dumpstr);
367  } else {
368  dump = rGen.InsState();
369  }
370  for(eit=rGen.AlphabetBegin();eit!=rGen.AlphabetEnd();++eit)
371  rGen.SetTransition(dump,*eit,dump);
372  bool dumpReached=false; // record, whether dump state is indeed used
373 
374  // if there is no initial state, the dump state becomes the initial state
375  if(rGen.InitStates().Empty()){
376  rGen.SetInitState(dump);
377  dumpReached=true;
378  }
379 
380  // introduce transitions to dumpstate (reference implementation)
381  /*
382  StateSet acc;
383  rGen.AccessibleSet(acc);
384  for (sit = acc.Begin(); sit != acc.End(); ++sit) {
385  for (eit = rGen.Alphabet().Begin(); eit != rGen.Alphabet().End(); ++eit) {
386  // If no transition is defined for this state and event, insert respective
387  // transition to dump state (note that dump state itself is also treated here
388  // and thus provided with selfloops)
389  if (rGen.TransRelBegin(*sit, *eit) == rGen.TransRelEnd(*sit, *eit)) {
390  rGen.SetTransition(*sit, *eit, dump);
391  // indicate that dumstate was reached
392  if(*sit!=dump) dumpReached=true;
393  }
394  }
395  }
396  */
397 
398 
399  // we can do faster ... but is this worth it?
400  Idx cs=0, ce=0;
401  StateSet acc = rGen.AccessibleSet();
402  sit=acc.Begin();
403  tit=rGen.TransRelBegin();
404  for(;sit!=acc.End();++sit) {
405  FD_DF("Automaton: processing state " << *sit);
406  cs=*sit;
407  // iterrate transrel to find current state cs
408  for(;tit!=rGen.TransRelEnd();++tit)
409  if(tit->X1 >= cs) break;
410  bool found= false;
411  if(tit!=rGen.TransRelEnd())
412  if(tit->X1 == cs) found=true;
413  // current state not found, so all transitions go to dump
414  if(!found) {
415  FD_DF("Automaton: state not found, all transitions go to dump");
416  for(eit=rGen.AlphabetBegin();eit!=rGen.AlphabetEnd();++eit)
417  rGen.SetTransition(cs,*eit,dump);
418  if(cs!=dump) dumpReached=true;
419  continue;
420  }
421  // current state found, search for enabled events
422  eit=rGen.AlphabetBegin();
423  while(tit!=rGen.TransRelEnd()) {
424  // event to resolve
425  ce=*eit;
426  FD_DF("Automaton: processing " << tit->Str() << " awaiting " << ce);
427  while(eit!=rGen.AlphabetEnd()) {
428  ce=*eit;
429  if(ce==tit->Ev) break;
430  // add missing transition to dump
431  FD_DF("Automaton: add " << cs << "-(" << ce << ")->dump");
432  rGen.SetTransition(cs,ce,dump);
433  if(cs!=dump) dumpReached=true;
434  // look for next event
435  ++eit;
436  }
437  // all events resolved, go for next state
438  if(eit==rGen.AlphabetEnd()) break;
439  // all events up to ce have been resolved
440  // test whether we have more transitions for the current state
441  bool fin=false;
442  while(tit!=rGen.TransRelEnd()) {
443  ++tit;
444  if(tit==rGen.TransRelEnd()) {fin=true; break;}
445  if(tit->X1!=cs) {fin=true; break;}
446  if(tit->Ev!=ce) break;
447  FD_DF("Automaton: skip " << tit->Str());
448  }
449  // there are more transitions to consider, so resolve the next event
450  if(!fin) {
451  ++eit;
452  continue;
453  }
454  // we did ran out transitions, so complete this state
455  ++eit;
456  while(eit != rGen.AlphabetEnd()) {
457  FD_DF("Automaton: fin " << cs << "-(" << *eit << ")->dump");
458  rGen.SetTransition(cs,*eit,dump);
459  if(cs!=dump) dumpReached=true;
460  ++eit;
461  }
462  break;
463  }
464  }
465 
466  // if no transition was introduced (except for selfloops), remove dump state
467  if(!dumpReached) {
468  rGen.DelState(dump);
469  dump=0;
470  }
471 
472  return dump;
473 }
474 
475 // API warpper Automaton(rGen,rRes)
476 Idx Automaton(const Generator& rGen, Generator& rRes) {
477  FD_DF("Automaton("<< rGen.Name() << ", ...)");
478  rRes=rGen;
479  return Automaton(rRes);
480 }
481 
482 // Automaton(rGen)
484  FD_DF("Automaton("<< rGen.Name() << ")");
485  std::string name=rGen.Name();
486  Idx ds=Automaton(rGen,rGen.Alphabet());
487  rGen.Name(CollapsString("Automaton(" + name + ")"));
488  return ds;
489 }
490 
491 // LanguageComplement(rGen,rAlphabet)
492 void LanguageComplement(Generator& rGen, const EventSet& rAlphabet) {
493  FD_DF("LanguageComplement("<< rGen.Name() << "," << rAlphabet.Name() << ")");
494 
495  // fix name
496  std::string name = rGen.Name();
497 
498  // convert to automaton (avoiding statename "dump")
499  bool stateNamesEnabled=rGen.StateNamesEnabled();
500  rGen.StateNamesEnabled(false);
501  rGen.Trim();
502  Automaton(rGen,rAlphabet);
503  rGen.StateNamesEnabled(stateNamesEnabled);
504 
505  // invert marking
506  rGen.InjectMarkedStates(rGen.States() - rGen.MarkedStates());
507 
508  // set name
509  rGen.Name(CollapsString("Complement(" + name + "," + rAlphabet.Name() + ")"));
510 }
511 
512 // LanguageComplement(rGen)
514  FD_DF("LanguageComplement("<< rGen.Name() << ")");
515  std::string name=rGen.Name();
516  LanguageComplement(rGen,rGen.Alphabet());
517  rGen.Name(CollapsString("Complement(" + name + ")"));
518  return;
519 }
520 
521 // language complement, uniform api
522 void LanguageComplement(const Generator& rGen, Generator& rRes) {
523  rRes=rGen;
524  LanguageComplement(rRes);
525 }
526 
527 
528 // language complement, uniform api
529 void LanguageComplement(const Generator& rGen, const EventSet& rSigma, Generator& rRes) {
530  rRes=rGen;
531  LanguageComplement(rRes,rSigma);
532 }
533 
534 
535 
536 
537 //LanguageDifference(rGen1, rGen2, rResGen)
539  const Generator& rGen1,
540  const Generator& rGen2,
541  Generator& rResGen) {
542 
543  FD_DF("LanguageDifference("<< rGen1.Name() << "," << rGen2.Name() << ")");
544 
545  // incl. all-empty case
546  if(IsEmptyLanguage(rGen2)) {
547  rResGen.Assign(rGen1);
548  rResGen.Name(CollapsString("LanguageDifference(" + rGen1.Name() + "," + rGen2.Name() + ")"));
549  return;
550  }
551 
552  // use pointer pResGen to result rResGen
553  Generator* pResGen = &rResGen;
554  if(&rResGen == &rGen1 || &rResGen== &rGen2) {
555  pResGen = rResGen.New();
556  }
557 
558  // due to the use of LanguageComplement(), rGen2 has to be deterministic
559  #ifdef FAUDES_CHECKED
560  if(!(rGen2.IsDeterministic())){
561  std::stringstream errstr;
562  errstr << "Nondeterministic parameter " << rGen2.Name() << ".";
563  throw Exception("LanguageDifference()", errstr.str(), 101);
564  }
565  #endif
566 
567  // prepare result
568  pResGen->Clear();
569 
570  // calculate "Lm1-Lm2" by building the intersection of Lm1 with the complement of Lm2
571  // for correct result, complement has to be computed wrt the alphabet of Lm1 (!)
572 
573  *pResGen=rGen2;
574  LanguageComplement(*pResGen,rGen1.Alphabet());
575  LanguageIntersection(rGen1, *pResGen, *pResGen);
576 
577  FD_DF("LanguageDifference(...): stage 2");
578 
579  // if necessary, move pResGen to rResGen
580  if(pResGen != &rResGen) {
581  pResGen->Move(rResGen);
582  delete pResGen;
583  }
584 
585  FD_DF("LanguageDifference(...): done");
586  return;
587 }
588 
589 // LanguageConcatenateNonDet(rGen1, rGen2, rResGen)
590 void LanguageConcatenateNonDet(const Generator& rGen1, const Generator& rGen2,
591  Generator& rResGen) {
592  FD_DF("LanguageConcatenateNonDet(" << rGen1.Name() << "," << rGen2.Name() << ")");
593 
594  // are state names enabled in result?
595  bool stateNamesEnabled=rResGen.StateNamesEnabled();
596 
597  // use pointer pResGen to result rResGen
598  Generator* pResGen = &rResGen;
599  if(&rResGen== &rGen1 || &rResGen== &rGen2) {
600  pResGen= rResGen.New();
601  }
602 
603  // prepare result
604  pResGen->Clear();
605 
606  // union of alphabets
607  pResGen->InjectAlphabet(rGen1.Alphabet() + rGen2.Alphabet());
608 
609  // Maps from states of rGen1 and rGen2 to states of ResGen
610  std::map<Idx,Idx> Gen1StatesMap;
611  std::map<Idx,Idx> Gen2StatesMap;
612 
613  // helpers
614  StateSet::Iterator sit;
615  TransSet::Iterator tit;
616 
617  // "union" of states: insert states representing the states of rGen1 and rGen2
618  for (sit = rGen1.StatesBegin(); sit != rGen1.StatesEnd(); ++sit) {
619  if (stateNamesEnabled) {
620  Gen1StatesMap[*sit] = pResGen->InsState(pResGen->UniqueStateName(rGen1.StateName(*sit)+"(1)"));
621  } else {
622  Gen1StatesMap[*sit] = pResGen->InsState();
623  }
624  }
625  for (sit = rGen2.StatesBegin(); sit != rGen2.StatesEnd(); ++sit) {
626  if (stateNamesEnabled) {
627  Gen2StatesMap[*sit] = pResGen->InsState(pResGen->UniqueStateName(rGen2.StateName(*sit)+"(2)"));
628  } else {
629  Gen2StatesMap[*sit] = pResGen->InsState();
630  }
631  }
632 
633  // "union" transitions: insert all rGen1 transitions
634  for (tit = rGen1.TransRelBegin(); tit != rGen1.TransRelEnd(); ++tit)
635  pResGen->SetTransition(Gen1StatesMap[tit->X1], tit->Ev, Gen1StatesMap[tit->X2]);
636 
637  // "union" transitions: insert all rGen2 transitions
638  for (tit = rGen2.TransRelBegin(); tit != rGen2.TransRelEnd(); ++tit)
639  pResGen->SetTransition(Gen2StatesMap[tit->X1], tit->Ev, Gen2StatesMap[tit->X2]);
640 
641 
642  // initial state bug (detected by Tomas Masopust, fix by Klaus Schmidt)
643  // 1) copy all transitions to the result, clear initial/marked status
644  // 2) all initial states of G1 become initial states in the result
645  // 3) if L1 contains the empty string, also all initial states of G2 become initial states
646  // in the result
647  // 4) transition leading to a marked state in G1 also become transitions to all
648  // initial states of G2
649  // 5) marked states of G2 become marked in the result
650 
651 
652  // test whether L1 includes the empty string
653  bool concatenateEpsilon1=false;
654  for(sit = rGen1.InitStatesBegin(); sit != rGen1.InitStatesEnd(); ++sit) {
655  if(rGen1.ExistsMarkedState(*sit)) {
656  concatenateEpsilon1=true;
657  break;
658  }
659  }
660 
661  // initial states of G1 become initial states in the result
662  for (sit = rGen1.InitStatesBegin(); sit != rGen1.InitStatesEnd(); ++sit)
663  pResGen->SetInitState(Gen1StatesMap[*sit]);
664 
665  // if L1 contains the emtystring, G2 initial states become initial states in the result
666  if(concatenateEpsilon1)
667  for (sit = rGen2.InitStatesBegin(); sit != rGen2.InitStatesEnd(); ++sit)
668  pResGen->SetInitState(Gen2StatesMap[*sit]);
669 
670  // any G1 transition to a marked state must also lead to all initial states of G2
671  for(tit = rGen1.TransRelBegin(); tit != rGen1.TransRelEnd(); ++tit)
672  if(rGen1.ExistsMarkedState(tit->X2))
673  for(sit = rGen2.InitStatesBegin(); sit != rGen2.InitStatesEnd(); ++sit)
674  pResGen->SetTransition(Gen1StatesMap[tit->X1], tit->Ev, Gen2StatesMap[*sit]);
675 
676  // set pResGen marked states corresponding to rGen2 marked states using Gen2StatesMap
677  for(sit = rGen2.MarkedStatesBegin(); sit != rGen2.MarkedStatesEnd(); ++sit) {
678  pResGen->SetMarkedState(Gen2StatesMap[*sit]);
679  }
680 
681  // remove blocking states as they provide no useful meaning.
682  pResGen->Trim();
683  pResGen->Name("ConcatenateNonDet("+rGen1.Name()+","+rGen2.Name()+")");
684 
685  // if necessary, move pResGen to rResGen
686  if(pResGen != &rResGen) {
687  pResGen->Move(rResGen);
688  delete pResGen;
689  }
690 
691 }
692 
693 // LanguageConcatenate(rGen1, rGen2, rResGen)
694 void LanguageConcatenate(const Generator& rGen1, const Generator& rGen2,
695  Generator& rResGen) {
696 
697  FD_DF("LanguageConcatenate("<< rGen1.Name()
698  << "," << rGen2.Name() << ")");
699 
700  // perform nondeterministic language concatenation
701  LanguageConcatenateNonDet(rGen1, rGen2, rResGen);
702 
703  // make deterministic if necessary
704  if(!(rResGen.IsDeterministic())){
705  Deterministic(rResGen, rResGen);
706  }
707 
708  // set name of result
709  rResGen.Name("Concatenate("+rGen1.Name()+","+rGen2.Name()+")");
710 
711  return;
712 }
713 
714 // FullLanguage(rAlphabet, rResGen)
715 void FullLanguage(const EventSet& rAlphabet, Generator& rResGen) {
716  FD_DF("FullLanguage("<< rAlphabet.Name()
717  << "," << rResGen.Name() << ")");
718 
719  // prepare result
720  rResGen.Clear();
721 
722  // helpers
723  Idx state;
724  EventSet::Iterator evit;
725 
726  // alphabet
727  rResGen.InjectAlphabet(rAlphabet);
728 
729  // insert marked initial state
730  if(rResGen.StateNamesEnabled()){
731  state = rResGen.InsInitState("1");
732  } else{
733  state = rResGen.InsInitState();
734  }
735  rResGen.SetMarkedState(state);
736 
737  // create selfloop for each event
738  for (evit = rAlphabet.Begin(); evit != rAlphabet.End(); ++evit) {
739  rResGen.SetTransition(state, *evit, state);
740  }
741 
742  // set name of result
743  rResGen.Name("FullLanguage("+rAlphabet.Name()+")");
744 
745  return;
746 }
747 
748 // AlphabetLanguage(rAlphabet, rResGen)
749 void AlphabetLanguage(const EventSet& rAlphabet, Generator& rResGen) {
750  FD_DF("AlphabetLanguage("<< rAlphabet.Name()
751  << "," << rResGen.Name() << ")");
752 
753  // prepare result
754  rResGen.Clear();
755 
756  // set name of result
757  rResGen.Name("AlphabetLanguage("+rAlphabet.Name()+")");
758 
759  // if alphabet is empty, leave generator empty
760  if(rAlphabet.Empty()){
761  FD_WARN("AlphabetLanguage: empty alphabet.");
762  return;
763  }
764 
765  // helpers
766  Idx istate, mstate;
767  EventSet::Iterator evit;
768 
769  // alphabet
770  rResGen.InjectAlphabet(rAlphabet);
771 
772  // insert one initial state and one marked state
773  if(rResGen.StateNamesEnabled()){
774  istate = rResGen.InsInitState("1");
775  mstate = rResGen.InsMarkedState("2");
776  }
777  else{
778  istate = rResGen.InsInitState();
779  mstate = rResGen.InsMarkedState();
780  }
781 
782  // for each event from rAlphabet, inserted transition leading from init state to marked state
783  for (evit = rAlphabet.Begin(); evit != rAlphabet.End(); ++evit) {
784  rResGen.SetTransition(istate, *evit, mstate);
785  }
786 
787  return;
788 }
789 
790 // EmptyStringLanguage(rAlphabet, rResGen)
791 void EmptyStringLanguage(const EventSet& rAlphabet, Generator& rResGen) {
792  FD_DF("EmptyStringLanguage("<< rAlphabet.Name()
793  << "," << rResGen.Name() << ")");
794 
795  // prepare result
796  rResGen.Clear();
797 
798  // helpers
799  Idx state;
800 
801  // alphabet
802  rResGen.InjectAlphabet(rAlphabet);
803 
804  // insert marked initial state
805  if(rResGen.StateNamesEnabled()){
806  state = rResGen.InsInitState("1");
807  }
808  else{
809  state = rResGen.InsInitState();
810  }
811  rResGen.SetMarkedState(state);
812 
813  // set name of result
814  rResGen.Name("EmptyStringLanguage("+rAlphabet.Name()+")");
815 
816  return;
817 }
818 
819 // EmptyLanguage(rAlphabet, rResGen)
820 void EmptyLanguage(const EventSet& rAlphabet, Generator& rResGen) {
821  FD_DF("EmptyStringLanguage("<< rAlphabet.Name()
822  << "," << rResGen.Name() << ")");
823 
824  // prepare result
825  rResGen.Clear();
826 
827  // set alphabet
828  rResGen.InjectAlphabet(rAlphabet);
829 
830  // set name of result
831  rResGen.Name("EmptyLanguage("+rAlphabet.Name()+")");
832 
833  return;
834 }
835 
836 // EmptyLanguage(rGen)
837 bool IsEmptyLanguage(const Generator& rGen) {
838  // case a) check if set of marked or initial states is empty
839  if(rGen.MarkedStatesSize()==0) return true;
840  if(rGen.InitStatesSize()==0) return true;
841  // case b) check if no marked state is accessible (reachable)
842  return (rGen.AccessibleSet()*rGen.MarkedStates()).Empty();
843 }
844 
845 // LanguageInclusion(rGen1, rGen2)
846 bool LanguageInclusion(const Generator& rGen1, const Generator& rGen2) {
847 
848  FD_DF("LanguageInclusion("<< rGen1.Name() << "," << rGen2.Name() << ")");
849 
850  // check if there is no string in Lm1 that is not in Lm2, which means Lm1<=Lm2
851  Generator NotrGen2=rGen2;
852  NotrGen2.StateNamesEnabled(false);
853  // note: complement w.r.t. union of alphabets to ensure that elementwise
854  // inclusion of Lm1 in Lm2 is tested
855  LanguageComplement(NotrGen2 , rGen1.Alphabet()+rGen2.Alphabet());
856  return EmptyLanguageIntersection(rGen1,NotrGen2);
857 }
858 
859 // LanguageEquality(rGen1, rGen2)
860 bool LanguageEquality(const Generator& rGen1, const Generator& rGen2) {
861 
862  FD_DF("LanguageEquality("<< rGen1.Name() << "," << rGen2.Name() << ")");
863 
864  // Check for equality by testing mutual inclusion
865  return LanguageInclusion(rGen1,rGen2) && LanguageInclusion(rGen2,rGen1);
866 }
867 
868 // KleeneClosure(rGen)
870 
871  FD_DF("KleeneClosure("<< rGen.Name() << ")");
872 
873  // fix name
874  std::string name=CollapsString("KleeneClosure(" + rGen.Name() + ")");
875 
876  // The Kleene Closure of the empty set is the empty set
877  if(IsEmptyLanguage(rGen)){
878  rGen.Clear();
879  rGen.Name(name);
880  return;
881  }
882 
883  // run nondet version
884  KleeneClosureNonDet(rGen);
885  Deterministic(rGen, rGen);
886 
887  // set name
888  rGen.Name(name);
889 }
890 
891 // KleeneClosure(rGen, rResGen)
892 void KleeneClosure(const Generator& rGen, Generator& rResGen) {
893 
894  FD_DF("KleeneClosure("<< rGen.Name() << ", ... )");
895 
896  // if arg and result match, call respective version
897  if(&rGen==&rResGen) {
898  KleeneClosure(rResGen);
899  return;
900  }
901 
902  // fix name
903  std::string name=CollapsString("KleeneClosure(" + rGen.Name() + ")");
904 
905  // The Kleene Closure of the empty set is the empty set
906  if(IsEmptyLanguage(rGen)){
907  rResGen.Clear();
908  rResGen.Name(name);
909  return;
910  }
911 
912  // run nondet version with intermediate result
913  Generator* pgen=rGen.Copy();
914  KleeneClosureNonDet(*pgen);
915  Deterministic(*pgen, rResGen);
916  delete pgen;
917 
918  // set name
919  rResGen.Name(name);
920 }
921 
922 // KleeneClosureNonDet(rGen)
924 
925  FD_DF("KleeneClosureNonDet("<< rGen.Name() << ")");
926 
927  // set name
928  rGen.Name(CollapsString("KleeneClosureNonDet("+ rGen.Name() + ")"));
929 
930  // make accessible (relevant)
931  rGen.Accessible();
932 
933  // test for empty language
934  if(rGen.MarkedStatesSize()==0) {
935  rGen.Clear();
936  return;
937  }
938 
939  // helpers
940  TransSet::Iterator tit;
941  TransSet TransToInsert;
942 
943  // initial state bug (detected by Tomas Masopust, fixes proposed by Klaus Schmidt and Florian Frohn)
944  // 1. prepare the generator to have a unique initial state
945  // 2. if the initial state fails to be marked, introduce an alternative marked initial state.
946  // 3. equip the markded initial state with the same transitions as the original initial state
947  UniqueInit(rGen);
948  Idx istate = *rGen.InitStatesBegin();
949  Idx imstate = istate;
950  if(!rGen.ExistsMarkedState(imstate)) {
951  imstate=rGen.InsInitState();
952  rGen.SetMarkedState(imstate);
953  for(tit = rGen.TransRelBegin(istate); tit != rGen.TransRelEnd(istate); ++tit) {
954  TransToInsert.Insert(imstate, tit->Ev, tit->X2);
955  }
956  for (tit = TransToInsert.Begin(); tit != TransToInsert.End(); ++tit) {
957  rGen.SetTransition(*tit);
958  }
959  TransToInsert.Clear();
960  rGen.ClrInitState(istate);
961  }
962  rGen.Accessible(); // cosmetic
963 
964 
965  // for all transitions leading from a state x1 to a marked state: insert a transition
966  // with the same event that leads to the unique marked initial state.
967  for(tit = rGen.TransRelBegin(); tit != rGen.TransRelEnd(); ++tit) {
968  if(rGen.ExistsMarkedState(tit->X2)) {
969  if(!(rGen.ExistsTransition(tit->X1, tit->Ev, imstate)) ){
970  TransToInsert.Insert(tit->X1, tit->Ev, imstate);
971  }
972  }
973  }
974  for (tit = TransToInsert.Begin(); tit != TransToInsert.End(); ++tit) {
975  rGen.SetTransition(*tit);
976  }
977 
978 }
979 
980 // PrefixClosure(rGen)
982 
983  FD_DF("PrefixClosure("<< rGen.Name() << ")");
984 
985  // fix name
986  std::string name=CollapsString("PrefixClosure("+ rGen.Name() + ")");
987 
988  // remove all states that do net represent prefixes of marked strings
989  rGen.Coaccessible();
990 
991  // mark all remaining states
992  rGen.InjectMarkedStates(rGen.States());
993 
994  // set name
995  rGen.Name(name);
996 
997 }
998 
999 // IsClosed
1000 bool IsClosed(const Generator& rGen) {
1001 
1002  // figure relevant states
1003  StateSet relevant = rGen.AccessibleSet() * rGen.CoaccessibleSet();
1004 
1005  // test
1006  return relevant <= rGen.MarkedStates();
1007 
1008 }
1009 
1010 // IsNonblocking
1011 bool IsNonblocking(const Generator& rGen) {
1012 
1013  // test
1014  return rGen.AccessibleSet() <= rGen.CoaccessibleSet();
1015 
1016 }
1017 
1018 // IsNonblocking
1019 bool IsNonblocking(const Generator& rGen1, const Generator& rGen2) {
1020 
1021  // build composition
1022  Generator parallel;
1023  parallel.StateNamesEnabled(false);
1024  Parallel(rGen1,rGen2,parallel);
1025 
1026  // test (parallel returns an accessible generator).
1027  return parallel.States() <= parallel.CoaccessibleSet();
1028 
1029 }
1030 
1031 
1032 
1033 // SelfLoop(rGen,rAlphabet)
1034 void SelfLoop(Generator& rGen,const EventSet& rAlphabet) {
1035 
1036  FD_DF("SelfLoop(" << rGen.Name() << "," << rAlphabet.Name() << ")");
1037 
1038  // fix name
1039  std::string name = CollapsString("SelfLoop(" + rGen.Name() + "," + rAlphabet.Name() + ")");
1040  // extend alphabet of rGen
1041  rGen.InjectAlphabet(rGen.Alphabet()+rAlphabet);
1042 
1043  //helpers
1044  EventSet::Iterator evit,evbegin,evend;
1045  evbegin = rAlphabet.Begin();
1046  evend = rAlphabet.End();
1047  StateSet::Iterator sit;
1048 
1049  // iterate over all states and insert selfloop for each event of rAlphabet
1050  for (sit = rGen.StatesBegin(); sit != rGen.StatesEnd(); ++sit) {
1051  for(evit = evbegin; evit != evend; ++evit){
1052  rGen.SetTransition(*sit, *evit, *sit);
1053  }
1054  }
1055 
1056  // set name
1057  rGen.Name(name);
1058 }
1059 
1060 // SelfLoopMarkedStates(rGen,rAlphabet)
1061 void SelfLoopMarkedStates(Generator& rGen,const EventSet& rAlphabet) {
1062 
1063  FD_DF("SelfLoopMarkedStates(" << rGen.Name() << "," << rAlphabet.Name() << ")");
1064 
1065  // fix name
1066  std::string name = CollapsString("SelfLoopMarkedStates(" + rGen.Name()
1067  + "," + rAlphabet.Name() + ")");
1068 
1069  // extend alphabet of rGen
1070  rGen.InjectAlphabet(rGen.Alphabet()+rAlphabet);
1071 
1072  //helpers
1073  EventSet::Iterator evit,evbegin,evend;
1074  evbegin = rAlphabet.Begin();
1075  evend = rAlphabet.End();
1076  StateSet::Iterator sit;
1077 
1078  // iterate over all marked states and insert selfloop for each event of rAlphabet
1079  for (sit = rGen.MarkedStatesBegin(); sit != rGen.MarkedStatesEnd(); ++sit) {
1080  for(evit = evbegin; evit != evend; ++evit){
1081  rGen.SetTransition(*sit, *evit, *sit);
1082  }
1083  }
1084 
1085  // set name
1086  rGen.Name(name);
1087 }
1088 
1089 // SelfLoop(rGen,rAlphabet,rStates)
1090 void SelfLoop(Generator& rGen,const EventSet& rAlphabet,const StateSet& rStates) {
1091 
1092  FD_DF("SelfLoop(" << rGen.Name() << "," << rAlphabet.Name() << "," << rStates.Name() << ")");
1093 
1094  // fix name
1095  std::string name = CollapsString("SelfLoop(" + rGen.Name()
1096  + "," + rAlphabet.Name() + "," + rStates.Name() + ")");
1097 
1098  // exception: rStates must be states of rGen
1099 #ifdef FAUDES_CHECKED
1100  if( !(rStates <= rGen.States()) ){
1101  std::stringstream errstr;
1102  errstr << "State set " << rStates.Name() <<
1103  " has to be included in state set of "<< rGen.Name() << ".";
1104  throw Exception("SelfLoop()", errstr.str(), 100);
1105  }
1106 #endif
1107 
1108  // extend alphabet of rGen
1109  rGen.InjectAlphabet(rGen.Alphabet()+rAlphabet);
1110 
1111  //helpers
1112  EventSet::Iterator evit,evbegin,evend;
1113  evbegin = rAlphabet.Begin();
1114  evend = rAlphabet.End();
1115  StateSet::Iterator sit;
1116 
1117  // iterate over all marked states and insert selfloop for each event of rAlphabet
1118  for (sit = rStates.Begin(); sit != rStates.End(); ++sit) {
1119  for(evit = evbegin; evit != evend; ++evit){
1120  rGen.SetTransition(*sit, *evit, *sit);
1121  }
1122  }
1123 
1124  // set name
1125  rGen.Name(name);
1126 }
1127 
1128 /** legacy wrapper, pre 2.33d */
1129 bool IsPrefixClosed(const Generator& rGen) {
1130  FD_WARN("IsPrefixClosed(): API depreciated, use IsClosed()");
1131  return IsClosed(rGen);
1132 }
1133 
1134 } // namespace faudes
1135 
1136 #undef Product //see define above for comment
#define FD_WPC(cntnow, contdone, message)
#define FD_WARN(message)
#define FD_DF(message)
#define FD_ERR(message)
const std::string & Name(void) const
Definition: cfl_types.cpp:422
std::vector< int >::size_type Position
virtual const T & At(const Position &pos) const
Iterator Begin(void) const
Iterator End(void) const
bool Insert(const Transition &rTransition)
TBaseSet< Transition, TransSort::X1EvX2 >::Iterator Iterator
Definition: cfl_transset.h:273
void Write(const Type *pContext=0) const
Definition: cfl_types.cpp:145
Idx Size(void) const
StateSet::Iterator StatesBegin(void) const
StateSet::Iterator InitStatesBegin(void) const
bool SetTransition(Idx x1, Idx ev, Idx x2)
const StateSet & MarkedStates(void) const
const EventSet & Alphabet(void) const
virtual void Move(vGenerator &rGen)
virtual vGenerator & Assign(const Type &rSrc)
virtual vGenerator * Copy(void) const
const StateSet & InitStates(void) const
TransSet::Iterator TransRelBegin(void) const
Idx InitStatesSize(void) const
EventSet::Iterator AlphabetBegin(void) const
virtual vGenerator * New(void) const
bool ExistsTransition(const std::string &rX1, const std::string &rEv, const std::string &rX2) const
void InjectMarkedStates(const StateSet &rNewMarkedStates)
Idx MarkedStatesSize(void) const
void SetInitState(Idx index)
StateSet AccessibleSet(void) const
StateSet::Iterator MarkedStatesBegin(void) const
std::string StateName(Idx index) const
bool DelState(Idx index)
StateSet::Iterator StatesEnd(void) const
void ClrInitState(Idx index)
TransSet::Iterator TransRelEnd(void) const
bool IsDeterministic(void) const
StateSet::Iterator MarkedStatesEnd(void) const
void SetMarkedState(Idx index)
bool StateNamesEnabled(void) const
StateSet::Iterator InitStatesEnd(void) const
EventSet::Iterator AlphabetEnd(void) const
StateSet CoaccessibleSet(void) const
virtual void Clear(void)
bool ExistsMarkedState(Idx index) const
std::string UniqueStateName(const std::string &rName) const
const StateSet & States(void) const
void InjectAlphabet(const EventSet &rNewalphabet)
bool Empty(void) const
Definition: cfl_baseset.h:1904
bool Exists(const T &rElem) const
Definition: cfl_baseset.h:2322
virtual void Clear(void)
Definition: cfl_baseset.h:2104
Iterator End(void) const
Definition: cfl_baseset.h:2098
Iterator Begin(void) const
Definition: cfl_baseset.h:2093
bool IsClosed(const Generator &rGen)
bool EmptyLanguageIntersection(const Generator &rGen1, const Generator &rGen2)
void FullLanguage(const EventSet &rAlphabet, Generator &rResGen)
void LanguageUnion(const Generator &rGen1, const Generator &rGen2, Generator &rResGen)
void LanguageConcatenateNonDet(const Generator &rGen1, const Generator &rGen2, Generator &rResGen)
void SelfLoop(Generator &rGen, const EventSet &rAlphabet)
Idx Automaton(Generator &rGen, const EventSet &rAlphabet)
bool LanguageDisjoint(const Generator &rGen1, const Generator &rGen2)
bool LanguageInclusion(const Generator &rGen1, const Generator &rGen2)
void UniqueInit(Generator &rGen)
void KleeneClosure(Generator &rGen)
void PrefixClosure(Generator &rGen)
void Product(const Generator &rGen1, const Generator &rGen2, Generator &rResGen)
void Deterministic(const Generator &rGen, Generator &rResGen)
void LanguageUnionNonDet(const Generator &rGen1, const Generator &rGen2, Generator &rResGen)
Definition: cfl_regular.cpp:45
void AlphabetLanguage(const EventSet &rAlphabet, Generator &rResGen)
void LanguageConcatenate(const Generator &rGen1, const Generator &rGen2, Generator &rResGen)
bool IsEmptyLanguage(const Generator &rGen)
bool LanguageEquality(const Generator &rGen1, const Generator &rGen2)
void LanguageDifference(const Generator &rGen1, const Generator &rGen2, Generator &rResGen)
void LanguageIntersection(const Generator &rGen1, const Generator &rGen2, Generator &rResGen)
void EmptyLanguage(const EventSet &rAlphabet, Generator &rResGen)
void Parallel(const Generator &rGen1, const Generator &rGen2, Generator &rResGen)
void LanguageComplement(Generator &rGen, const EventSet &rAlphabet)
void EmptyStringLanguage(const EventSet &rAlphabet, Generator &rResGen)
void KleeneClosureNonDet(Generator &rGen)
void SelfLoopMarkedStates(Generator &rGen, const EventSet &rAlphabet)
uint32_t Idx
bool IsNonblocking(const GeneratorVector &rGvec)
bool IsPrefixClosed(const Generator &rGen)
std::string CollapsString(const std::string &rString, unsigned int len)
Definition: cfl_utils.cpp:91

libFAUDES 2.33l --- 2025.09.16 --- c++ api documentaion by doxygen