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 void 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  // trim (this used to be coaccessible only until 2024)
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  for (sit = rGen.StatesBegin(); sit != rGen.StatesEnd(); ++sit) {
383  for (eit = rGen.Alphabet().Begin(); eit != rGen.Alphabet().End(); ++eit) {
384  // If no transition is defined for this state and event, insert respective
385  // transition to dump state (note that dump state itself is also treated here
386  // and thus provided with selfloops)
387  if (rGen.TransRelBegin(*sit, *eit) == rGen.TransRelEnd(*sit, *eit)) {
388  rGen.SetTransition(*sit, *eit, dump);
389  // indicate that dumstate was reached
390  if(*sit!=dump) dumpReached=true;
391  }
392  }
393  }
394  */
395 
396 
397  // we can do faster ... but is this worth it?
398  Idx cs=0, ce=0;
399  tit=rGen.TransRelBegin();
400  sit=rGen.StatesBegin();
401  for(;sit!=rGen.StatesEnd();++sit) {
402  FD_DF("Automaton: processing state " << *sit);
403  cs=*sit;
404  // iterrate transrel to find current state cs
405  for(;tit!=rGen.TransRelEnd();++tit)
406  if(tit->X1 >= cs) break;
407  bool found= false;
408  if(tit!=rGen.TransRelEnd())
409  if(tit->X1 == cs) found=true;
410  // current state not found, so all transitions to go to dump
411  if(!found) {
412  FD_DF("Automaton: state not found, all transitions go to dump");
413  for(eit=rGen.AlphabetBegin();eit!=rGen.AlphabetEnd();++eit)
414  rGen.SetTransition(cs,*eit,dump);
415  if(cs!=dump) dumpReached=true;
416  continue;
417  }
418  // current state found, search for enabled events
419  eit=rGen.AlphabetBegin();
420  while(tit!=rGen.TransRelEnd()) {
421  // event to resolve
422  ce=*eit;
423  FD_DF("Automaton: processing " << tit->Str() << " awaiting " << ce);
424  while(eit!=rGen.AlphabetEnd()) {
425  ce=*eit;
426  if(ce==tit->Ev) break;
427  // add missing transition to dump
428  FD_DF("Automaton: add " << cs << "-(" << ce << ")->dump");
429  rGen.SetTransition(cs,ce,dump);
430  if(cs!=dump) dumpReached=true;
431  // look for next event
432  ++eit;
433  }
434  // all events resolved, go for next state
435  if(eit==rGen.AlphabetEnd()) break;
436  // all events up to ce have been resolved
437  // test whether we have more transitions for the current state
438  bool fin=false;
439  while(tit!=rGen.TransRelEnd()) {
440  ++tit;
441  if(tit==rGen.TransRelEnd()) {fin=true; break;}
442  if(tit->X1!=cs) {fin=true; break;}
443  if(tit->Ev!=ce) break;
444  FD_DF("Automaton: skip " << tit->Str());
445  }
446  // there are more transitions to consider, so resolve the next event
447  if(!fin) {
448  ++eit;
449  continue;
450  }
451  // we did ran out transitions, so complete this state
452  ++eit;
453  while(eit != rGen.AlphabetEnd()) {
454  FD_DF("Automaton: fin " << cs << "-(" << *eit << ")->dump");
455  rGen.SetTransition(cs,*eit,dump);
456  if(cs!=dump) dumpReached=true;
457  ++eit;
458  }
459  break;
460  }
461  }
462 
463  // if no transition was introduced (except for selfloops), remove dump state
464  if(!dumpReached)
465  rGen.DelState(dump);
466 }
467 
468 // API warpper Automaton(rGen,rRes)
469 void Automaton(const Generator& rGen, Generator& rRes) {
470  FD_DF("Automaton("<< rGen.Name() << ", ...)");
471  rRes=rGen;
472  Automaton(rRes);
473 }
474 
475 // Automaton(rGen)
476 void Automaton(Generator& rGen) {
477  FD_DF("Automaton("<< rGen.Name() << ")");
478  std::string name=rGen.Name();
479  Automaton(rGen,rGen.Alphabet());
480  rGen.Name(CollapsString("Automaton(" + name + ")"));
481 }
482 
483 // LanguageComplement(rGen,rAlphabet)
484 void LanguageComplement(Generator& rGen, const EventSet& rAlphabet) {
485  FD_DF("LanguageComplement("<< rGen.Name() << "," << rAlphabet.Name() << ")");
486 
487  // fix name
488  std::string name = rGen.Name();
489 
490  // convert to automaton (avoiding statename "dump")
491  bool stateNamesEnabled=rGen.StateNamesEnabled();
492  rGen.StateNamesEnabled(false);
493  Automaton(rGen,rAlphabet);
494  rGen.StateNamesEnabled(stateNamesEnabled);
495 
496  // invert marking
497  rGen.InjectMarkedStates(rGen.States() - rGen.MarkedStates());
498 
499  // set name
500  rGen.Name(CollapsString("Complement(" + name + "," + rAlphabet.Name() + ")"));
501 }
502 
503 // LanguageComplement(rGen)
505  FD_DF("LanguageComplement("<< rGen.Name() << ")");
506  std::string name=rGen.Name();
507  LanguageComplement(rGen,rGen.Alphabet());
508  rGen.Name(CollapsString("Complement(" + name + ")"));
509  return;
510 }
511 
512 // language complement, uniform api
513 void LanguageComplement(const Generator& rGen, Generator& rRes) {
514  rRes=rGen;
515  LanguageComplement(rRes);
516 }
517 
518 
519 // language complement, uniform api
520 void LanguageComplement(const Generator& rGen, const EventSet& rSigma, Generator& rRes) {
521  rRes=rGen;
522  LanguageComplement(rRes,rSigma);
523 }
524 
525 
526 
527 
528 //LanguageDifference(rGen1, rGen2, rResGen)
530  const Generator& rGen1,
531  const Generator& rGen2,
532  Generator& rResGen) {
533 
534  FD_DF("LanguageDifference("<< rGen1.Name() << "," << rGen2.Name() << ")");
535 
536  // incl. all-empty case
537  if(IsEmptyLanguage(rGen2)) {
538  rResGen.Assign(rGen1);
539  rResGen.Name(CollapsString("LanguageDifference(" + rGen1.Name() + "," + rGen2.Name() + ")"));
540  return;
541  }
542 
543  // use pointer pResGen to result rResGen
544  Generator* pResGen = &rResGen;
545  if(&rResGen == &rGen1 || &rResGen== &rGen2) {
546  pResGen = rResGen.New();
547  }
548 
549  // due to the use of LanguageComplement(), rGen2 has to be deterministic
550  #ifdef FAUDES_CHECKED
551  if(!(rGen2.IsDeterministic())){
552  std::stringstream errstr;
553  errstr << "Nondeterministic parameter " << rGen2.Name() << ".";
554  throw Exception("LanguageDifference()", errstr.str(), 101);
555  }
556  #endif
557 
558  // prepare result
559  pResGen->Clear();
560 
561  // calculate "Lm1-Lm2" by building the intersection of Lm1 with the complement of Lm2
562  // for correct result, complement has to be computed wrt the alphabet of Lm1 (!)
563 
564  *pResGen=rGen2;
565  LanguageComplement(*pResGen,rGen1.Alphabet());
566  LanguageIntersection(rGen1, *pResGen, *pResGen);
567 
568  FD_DF("LanguageDifference(...): stage 2");
569 
570  // if necessary, move pResGen to rResGen
571  if(pResGen != &rResGen) {
572  pResGen->Move(rResGen);
573  delete pResGen;
574  }
575 
576  FD_DF("LanguageDifference(...): done");
577  return;
578 }
579 
580 // LanguageConcatenateNonDet(rGen1, rGen2, rResGen)
581 void LanguageConcatenateNonDet(const Generator& rGen1, const Generator& rGen2,
582  Generator& rResGen) {
583  FD_DF("LanguageConcatenateNonDet(" << rGen1.Name() << "," << rGen2.Name() << ")");
584 
585  // are state names enabled in result?
586  bool stateNamesEnabled=rResGen.StateNamesEnabled();
587 
588  // use pointer pResGen to result rResGen
589  Generator* pResGen = &rResGen;
590  if(&rResGen== &rGen1 || &rResGen== &rGen2) {
591  pResGen= rResGen.New();
592  }
593 
594  // prepare result
595  pResGen->Clear();
596 
597  // union of alphabets
598  pResGen->InjectAlphabet(rGen1.Alphabet() + rGen2.Alphabet());
599 
600  // Maps from states of rGen1 and rGen2 to states of ResGen
601  std::map<Idx,Idx> Gen1StatesMap;
602  std::map<Idx,Idx> Gen2StatesMap;
603 
604  // helpers
605  StateSet::Iterator sit;
606  TransSet::Iterator tit;
607 
608  // "union" of states: insert states representing the states of rGen1 and rGen2
609  for (sit = rGen1.StatesBegin(); sit != rGen1.StatesEnd(); ++sit) {
610  if (stateNamesEnabled) {
611  Gen1StatesMap[*sit] = pResGen->InsState(pResGen->UniqueStateName(rGen1.StateName(*sit)+"(1)"));
612  } else {
613  Gen1StatesMap[*sit] = pResGen->InsState();
614  }
615  }
616  for (sit = rGen2.StatesBegin(); sit != rGen2.StatesEnd(); ++sit) {
617  if (stateNamesEnabled) {
618  Gen2StatesMap[*sit] = pResGen->InsState(pResGen->UniqueStateName(rGen2.StateName(*sit)+"(2)"));
619  } else {
620  Gen2StatesMap[*sit] = pResGen->InsState();
621  }
622  }
623 
624  // "union" transitions: insert all rGen1 transitions
625  for (tit = rGen1.TransRelBegin(); tit != rGen1.TransRelEnd(); ++tit)
626  pResGen->SetTransition(Gen1StatesMap[tit->X1], tit->Ev, Gen1StatesMap[tit->X2]);
627 
628  // "union" transitions: insert all rGen2 transitions
629  for (tit = rGen2.TransRelBegin(); tit != rGen2.TransRelEnd(); ++tit)
630  pResGen->SetTransition(Gen2StatesMap[tit->X1], tit->Ev, Gen2StatesMap[tit->X2]);
631 
632 
633  // initial state bug (detected by Tomas Masopust, fix by Klaus Schmidt)
634  // 1) copy all transitions to the result, clear initial/marked status
635  // 2) all initial states of G1 become initial states in the result
636  // 3) if L1 contains the empty string, also all initial states of G2 become initial states
637  // in the result
638  // 4) transition leading to a marked state in G1 also become transitions to all
639  // initial states of G2
640  // 5) marked states of G2 become marked in the result
641 
642 
643  // test whether L1 includes the empty string
644  bool concatenateEpsilon1=false;
645  for(sit = rGen1.InitStatesBegin(); sit != rGen1.InitStatesEnd(); ++sit) {
646  if(rGen1.ExistsMarkedState(*sit)) {
647  concatenateEpsilon1=true;
648  break;
649  }
650  }
651 
652  // initial states of G1 become initial states in the result
653  for (sit = rGen1.InitStatesBegin(); sit != rGen1.InitStatesEnd(); ++sit)
654  pResGen->SetInitState(Gen1StatesMap[*sit]);
655 
656  // if L1 contains the emtystring, G2 initial states become initial states in the result
657  if(concatenateEpsilon1)
658  for (sit = rGen2.InitStatesBegin(); sit != rGen2.InitStatesEnd(); ++sit)
659  pResGen->SetInitState(Gen2StatesMap[*sit]);
660 
661  // any G1 transition to a marked state must also lead to all initial states of G2
662  for(tit = rGen1.TransRelBegin(); tit != rGen1.TransRelEnd(); ++tit)
663  if(rGen1.ExistsMarkedState(tit->X2))
664  for(sit = rGen2.InitStatesBegin(); sit != rGen2.InitStatesEnd(); ++sit)
665  pResGen->SetTransition(Gen1StatesMap[tit->X1], tit->Ev, Gen2StatesMap[*sit]);
666 
667  // set pResGen marked states corresponding to rGen2 marked states using Gen2StatesMap
668  for(sit = rGen2.MarkedStatesBegin(); sit != rGen2.MarkedStatesEnd(); ++sit) {
669  pResGen->SetMarkedState(Gen2StatesMap[*sit]);
670  }
671 
672  // remove blocking states as they provide no useful meaning.
673  pResGen->Trim();
674  pResGen->Name("ConcatenateNonDet("+rGen1.Name()+","+rGen2.Name()+")");
675 
676  // if necessary, move pResGen to rResGen
677  if(pResGen != &rResGen) {
678  pResGen->Move(rResGen);
679  delete pResGen;
680  }
681 
682 }
683 
684 // LanguageConcatenate(rGen1, rGen2, rResGen)
685 void LanguageConcatenate(const Generator& rGen1, const Generator& rGen2,
686  Generator& rResGen) {
687 
688  FD_DF("LanguageConcatenate("<< rGen1.Name()
689  << "," << rGen2.Name() << ")");
690 
691  // perform nondeterministic language concatenation
692  LanguageConcatenateNonDet(rGen1, rGen2, rResGen);
693 
694  // make deterministic if necessary
695  if(!(rResGen.IsDeterministic())){
696  Deterministic(rResGen, rResGen);
697  }
698 
699  // set name of result
700  rResGen.Name("Concatenate("+rGen1.Name()+","+rGen2.Name()+")");
701 
702  return;
703 }
704 
705 // FullLanguage(rAlphabet, rResGen)
706 void FullLanguage(const EventSet& rAlphabet, Generator& rResGen) {
707  FD_DF("FullLanguage("<< rAlphabet.Name()
708  << "," << rResGen.Name() << ")");
709 
710  // prepare result
711  rResGen.Clear();
712 
713  // helpers
714  Idx state;
715  EventSet::Iterator evit;
716 
717  // alphabet
718  rResGen.InjectAlphabet(rAlphabet);
719 
720  // insert marked initial state
721  if(rResGen.StateNamesEnabled()){
722  state = rResGen.InsInitState("1");
723  } else{
724  state = rResGen.InsInitState();
725  }
726  rResGen.SetMarkedState(state);
727 
728  // create selfloop for each event
729  for (evit = rAlphabet.Begin(); evit != rAlphabet.End(); ++evit) {
730  rResGen.SetTransition(state, *evit, state);
731  }
732 
733  // set name of result
734  rResGen.Name("FullLanguage("+rAlphabet.Name()+")");
735 
736  return;
737 }
738 
739 // AlphabetLanguage(rAlphabet, rResGen)
740 void AlphabetLanguage(const EventSet& rAlphabet, Generator& rResGen) {
741  FD_DF("AlphabetLanguage("<< rAlphabet.Name()
742  << "," << rResGen.Name() << ")");
743 
744  // prepare result
745  rResGen.Clear();
746 
747  // set name of result
748  rResGen.Name("AlphabetLanguage("+rAlphabet.Name()+")");
749 
750  // if alphabet is empty, leave generator empty
751  if(rAlphabet.Empty()){
752  FD_WARN("AlphabetLanguage: empty alphabet.");
753  return;
754  }
755 
756  // helpers
757  Idx istate, mstate;
758  EventSet::Iterator evit;
759 
760  // alphabet
761  rResGen.InjectAlphabet(rAlphabet);
762 
763  // insert one initial state and one marked state
764  if(rResGen.StateNamesEnabled()){
765  istate = rResGen.InsInitState("1");
766  mstate = rResGen.InsMarkedState("2");
767  }
768  else{
769  istate = rResGen.InsInitState();
770  mstate = rResGen.InsMarkedState();
771  }
772 
773  // for each event from rAlphabet, inserted transition leading from init state to marked state
774  for (evit = rAlphabet.Begin(); evit != rAlphabet.End(); ++evit) {
775  rResGen.SetTransition(istate, *evit, mstate);
776  }
777 
778  return;
779 }
780 
781 // EmptyStringLanguage(rAlphabet, rResGen)
782 void EmptyStringLanguage(const EventSet& rAlphabet, Generator& rResGen) {
783  FD_DF("EmptyStringLanguage("<< rAlphabet.Name()
784  << "," << rResGen.Name() << ")");
785 
786  // prepare result
787  rResGen.Clear();
788 
789  // helpers
790  Idx state;
791 
792  // alphabet
793  rResGen.InjectAlphabet(rAlphabet);
794 
795  // insert marked initial state
796  if(rResGen.StateNamesEnabled()){
797  state = rResGen.InsInitState("1");
798  }
799  else{
800  state = rResGen.InsInitState();
801  }
802  rResGen.SetMarkedState(state);
803 
804  // set name of result
805  rResGen.Name("EmptyStringLanguage("+rAlphabet.Name()+")");
806 
807  return;
808 }
809 
810 // EmptyLanguage(rAlphabet, rResGen)
811 void EmptyLanguage(const EventSet& rAlphabet, Generator& rResGen) {
812  FD_DF("EmptyStringLanguage("<< rAlphabet.Name()
813  << "," << rResGen.Name() << ")");
814 
815  // prepare result
816  rResGen.Clear();
817 
818  // set alphabet
819  rResGen.InjectAlphabet(rAlphabet);
820 
821  // set name of result
822  rResGen.Name("EmptyLanguage("+rAlphabet.Name()+")");
823 
824  return;
825 }
826 
827 // EmptyLanguage(rGen)
828 bool IsEmptyLanguage(const Generator& rGen) {
829  // case a) check if set of marked or initial states is empty
830  if(rGen.MarkedStatesSize()==0) return true;
831  if(rGen.InitStatesSize()==0) return true;
832  // case b) check if no marked state is accessible (reachable)
833  return (rGen.AccessibleSet()*rGen.MarkedStates()).Empty();
834 }
835 
836 // LanguageInclusion(rGen1, rGen2)
837 bool LanguageInclusion(const Generator& rGen1, const Generator& rGen2) {
838 
839  FD_DF("LanguageInclusion("<< rGen1.Name() << "," << rGen2.Name() << ")");
840 
841  // check if there is no string in Lm1 that is not in Lm2, which means Lm1<=Lm2
842  Generator NotrGen2=rGen2;
843  NotrGen2.StateNamesEnabled(false);
844  // note: complement w.r.t. union of alphabets to ensure that elementwise
845  // inclusion of Lm1 in Lm2 is tested
846  LanguageComplement(NotrGen2 , rGen1.Alphabet()+rGen2.Alphabet());
847  return EmptyLanguageIntersection(rGen1,NotrGen2);
848 }
849 
850 // LanguageEquality(rGen1, rGen2)
851 bool LanguageEquality(const Generator& rGen1, const Generator& rGen2) {
852 
853  FD_DF("LanguageEquality("<< rGen1.Name() << "," << rGen2.Name() << ")");
854 
855  // Check for equality by testing mutual inclusion
856  return LanguageInclusion(rGen1,rGen2) && LanguageInclusion(rGen2,rGen1);
857 }
858 
859 // KleeneClosure(rGen)
861 
862  FD_DF("KleeneClosure("<< rGen.Name() << ")");
863 
864  // fix name
865  std::string name=CollapsString("KleeneClosure(" + rGen.Name() + ")");
866 
867  // The Kleene Closure of the empty set is the empty set
868  if(IsEmptyLanguage(rGen)){
869  rGen.Clear();
870  rGen.Name(name);
871  return;
872  }
873 
874  // run nondet version
875  KleeneClosureNonDet(rGen);
876  Deterministic(rGen, rGen);
877 
878  // set name
879  rGen.Name(name);
880 }
881 
882 // KleeneClosure(rGen, rResGen)
883 void KleeneClosure(const Generator& rGen, Generator& rResGen) {
884 
885  FD_DF("KleeneClosure("<< rGen.Name() << ", ... )");
886 
887  // if arg and result match, call respective version
888  if(&rGen==&rResGen) {
889  KleeneClosure(rResGen);
890  return;
891  }
892 
893  // fix name
894  std::string name=CollapsString("KleeneClosure(" + rGen.Name() + ")");
895 
896  // The Kleene Closure of the empty set is the empty set
897  if(IsEmptyLanguage(rGen)){
898  rResGen.Clear();
899  rResGen.Name(name);
900  return;
901  }
902 
903  // run nondet version with intermediate result
904  Generator* pgen=rGen.Copy();
905  KleeneClosureNonDet(*pgen);
906  Deterministic(*pgen, rResGen);
907  delete pgen;
908 
909  // set name
910  rResGen.Name(name);
911 }
912 
913 // KleeneClosureNonDet(rGen)
915 
916  FD_DF("KleeneClosureNonDet("<< rGen.Name() << ")");
917 
918  // set name
919  rGen.Name(CollapsString("KleeneClosureNonDet("+ rGen.Name() + ")"));
920 
921  // make accessible (relevant)
922  rGen.Accessible();
923 
924  // test for empty language
925  if(rGen.MarkedStatesSize()==0) {
926  rGen.Clear();
927  return;
928  }
929 
930  // helpers
931  TransSet::Iterator tit;
932  TransSet TransToInsert;
933 
934  // initial state bug (detected by Tomas Masopust, fixes proposed by Klaus Schmidt and Florian Frohn)
935  // 1. prepare the generator to have a unique initial state
936  // 2. if the initial state fails to be marked, introduce an alternative marked initial state.
937  // 3. equip the markded initial state with the same transitions as the original initial state
938  UniqueInit(rGen);
939  Idx istate = *rGen.InitStatesBegin();
940  Idx imstate = istate;
941  if(!rGen.ExistsMarkedState(imstate)) {
942  imstate=rGen.InsInitState();
943  rGen.SetMarkedState(imstate);
944  for(tit = rGen.TransRelBegin(istate); tit != rGen.TransRelEnd(istate); ++tit) {
945  TransToInsert.Insert(imstate, tit->Ev, tit->X2);
946  }
947  for (tit = TransToInsert.Begin(); tit != TransToInsert.End(); ++tit) {
948  rGen.SetTransition(*tit);
949  }
950  TransToInsert.Clear();
951  rGen.ClrInitState(istate);
952  }
953  rGen.Accessible(); // cosmetic
954 
955 
956  // for all transitions leading from a state x1 to a marked state: insert a transition
957  // with the same event that leads to the unique marked initial state.
958  for(tit = rGen.TransRelBegin(); tit != rGen.TransRelEnd(); ++tit) {
959  if(rGen.ExistsMarkedState(tit->X2)) {
960  if(!(rGen.ExistsTransition(tit->X1, tit->Ev, imstate)) ){
961  TransToInsert.Insert(tit->X1, tit->Ev, imstate);
962  }
963  }
964  }
965  for (tit = TransToInsert.Begin(); tit != TransToInsert.End(); ++tit) {
966  rGen.SetTransition(*tit);
967  }
968 
969 }
970 
971 // PrefixClosure(rGen)
973 
974  FD_DF("PrefixClosure("<< rGen.Name() << ")");
975 
976  // fix name
977  std::string name=CollapsString("PrefixClosure("+ rGen.Name() + ")");
978 
979  // remove all states that do net represent prefixes of marked strings
980  rGen.Coaccessible();
981 
982  // mark all remaining states
983  rGen.InjectMarkedStates(rGen.States());
984 
985  // set name
986  rGen.Name(name);
987 
988 }
989 
990 // IsClosed
991 bool IsClosed(const Generator& rGen) {
992 
993  // figure relevant states
994  StateSet relevant = rGen.AccessibleSet() * rGen.CoaccessibleSet();
995 
996  // test
997  return relevant <= rGen.MarkedStates();
998 
999 }
1000 
1001 // IsNonblocking
1002 bool IsNonblocking(const Generator& rGen) {
1003 
1004  // test
1005  return rGen.AccessibleSet() <= rGen.CoaccessibleSet();
1006 
1007 }
1008 
1009 // IsNonblocking
1010 bool IsNonblocking(const Generator& rGen1, const Generator& rGen2) {
1011 
1012  // build composition
1013  Generator parallel;
1014  parallel.StateNamesEnabled(false);
1015  Parallel(rGen1,rGen2,parallel);
1016 
1017  // test (parallel returns an accessible generator).
1018  return parallel.States() <= parallel.CoaccessibleSet();
1019 
1020 }
1021 
1022 
1023 
1024 // SelfLoop(rGen,rAlphabet)
1025 void SelfLoop(Generator& rGen,const EventSet& rAlphabet) {
1026 
1027  FD_DF("SelfLoop(" << rGen.Name() << "," << rAlphabet.Name() << ")");
1028 
1029  // fix name
1030  std::string name = CollapsString("SelfLoop(" + rGen.Name() + "," + rAlphabet.Name() + ")");
1031  // extend alphabet of rGen
1032  rGen.InjectAlphabet(rGen.Alphabet()+rAlphabet);
1033 
1034  //helpers
1035  EventSet::Iterator evit,evbegin,evend;
1036  evbegin = rAlphabet.Begin();
1037  evend = rAlphabet.End();
1038  StateSet::Iterator sit;
1039 
1040  // iterate over all states and insert selfloop for each event of rAlphabet
1041  for (sit = rGen.StatesBegin(); sit != rGen.StatesEnd(); ++sit) {
1042  for(evit = evbegin; evit != evend; ++evit){
1043  rGen.SetTransition(*sit, *evit, *sit);
1044  }
1045  }
1046 
1047  // set name
1048  rGen.Name(name);
1049 }
1050 
1051 // SelfLoopMarkedStates(rGen,rAlphabet)
1052 void SelfLoopMarkedStates(Generator& rGen,const EventSet& rAlphabet) {
1053 
1054  FD_DF("SelfLoopMarkedStates(" << rGen.Name() << "," << rAlphabet.Name() << ")");
1055 
1056  // fix name
1057  std::string name = CollapsString("SelfLoopMarkedStates(" + rGen.Name()
1058  + "," + rAlphabet.Name() + ")");
1059 
1060  // extend alphabet of rGen
1061  rGen.InjectAlphabet(rGen.Alphabet()+rAlphabet);
1062 
1063  //helpers
1064  EventSet::Iterator evit,evbegin,evend;
1065  evbegin = rAlphabet.Begin();
1066  evend = rAlphabet.End();
1067  StateSet::Iterator sit;
1068 
1069  // iterate over all marked states and insert selfloop for each event of rAlphabet
1070  for (sit = rGen.MarkedStatesBegin(); sit != rGen.MarkedStatesEnd(); ++sit) {
1071  for(evit = evbegin; evit != evend; ++evit){
1072  rGen.SetTransition(*sit, *evit, *sit);
1073  }
1074  }
1075 
1076  // set name
1077  rGen.Name(name);
1078 }
1079 
1080 // SelfLoop(rGen,rAlphabet,rStates)
1081 void SelfLoop(Generator& rGen,const EventSet& rAlphabet,const StateSet& rStates) {
1082 
1083  FD_DF("SelfLoop(" << rGen.Name() << "," << rAlphabet.Name() << "," << rStates.Name() << ")");
1084 
1085  // fix name
1086  std::string name = CollapsString("SelfLoop(" + rGen.Name()
1087  + "," + rAlphabet.Name() + "," + rStates.Name() + ")");
1088 
1089  // exception: rStates must be states of rGen
1090 #ifdef FAUDES_CHECKED
1091  if( !(rStates <= rGen.States()) ){
1092  std::stringstream errstr;
1093  errstr << "State set " << rStates.Name() <<
1094  " has to be included in state set of "<< rGen.Name() << ".";
1095  throw Exception("SelfLoop()", errstr.str(), 100);
1096  }
1097 #endif
1098 
1099  // extend alphabet of rGen
1100  rGen.InjectAlphabet(rGen.Alphabet()+rAlphabet);
1101 
1102  //helpers
1103  EventSet::Iterator evit,evbegin,evend;
1104  evbegin = rAlphabet.Begin();
1105  evend = rAlphabet.End();
1106  StateSet::Iterator sit;
1107 
1108  // iterate over all marked states and insert selfloop for each event of rAlphabet
1109  for (sit = rStates.Begin(); sit != rStates.End(); ++sit) {
1110  for(evit = evbegin; evit != evend; ++evit){
1111  rGen.SetTransition(*sit, *evit, *sit);
1112  }
1113  }
1114 
1115  // set name
1116  rGen.Name(name);
1117 }
1118 
1119 /** legacy wrapper, pre 2.33d */
1120 bool IsPrefixClosed(const Generator& rGen) {
1121  FD_WARN("IsPrefixClosed(): API depreciated, use IsClosed()");
1122  return IsClosed(rGen);
1123 }
1124 
1125 } // namespace faudes
1126 
1127 #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:1787
bool Exists(const T &rElem) const
Definition: cfl_baseset.h:2180
virtual void Clear(void)
Definition: cfl_baseset.h:1962
Iterator End(void) const
Definition: cfl_baseset.h:1956
Iterator Begin(void) const
Definition: cfl_baseset.h:1951
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)
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 Automaton(Generator &rGen, const EventSet &rAlphabet)
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.33h --- 2025.06.18 --- c++ api documentaion by doxygen