|
Go to the documentation of this file.
48 FD_DF( "LanguageUnionNonDet("<< rGen1. Name()
49 << "," << rGen2. Name() << ")");
57 if(&rResGen== &rGen1 || &rResGen== &rGen2) {
58 pResGen= rResGen. New();
68 std::map<Idx,Idx> Gen1StatesMap;
69 std::map<Idx,Idx> Gen2StatesMap;
72 StateSet::Iterator sit;
74 if (stateNamesEnabled) {
78 Gen1StatesMap[*sit] = pResGen-> InsState();
82 if (stateNamesEnabled) {
86 Gen2StatesMap[*sit] = pResGen-> InsState();
93 pResGen-> SetTransition(Gen1StatesMap[tit->X1], tit->Ev, Gen1StatesMap[tit->X2]);
96 pResGen-> SetTransition(Gen2StatesMap[tit->X1], tit->Ev, Gen2StatesMap[tit->X2]);
119 if(pResGen != &rResGen) {
120 pResGen-> Move(rResGen);
131 << "," << rGen2. Name() << ")");
134 std::string name1 = rGen1. Name();
135 std::string name2 = rGen2. Name();
158 if(rGenVec. Size()==0) {
163 if(rGenVec. Size()==1) {
164 rResGen=rGenVec. At(0);
190 FD_DF( "LanguageIntersection("<< rGen1. Name() << "," << rGen2. Name() << ")");
193 std::string name1 = rGen1. Name();
194 std::string name2 = rGen2. Name();
197 Product(rGen1, rGen2, rResGen);
199 FD_DF( "LanguageIntersection("<< rGen1. Name() << "," << rGen2. Name() << "): done");
209 if(rGenVec. Size()==0) {
214 if(rGenVec. Size()==1) {
215 rResGen=rGenVec. At(0);
228 FD_DF( "EmptyLanguageIntersection("<< rGen1. Name()
229 << "," << rGen2. Name() << ")");
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);
243 std::stack< std::pair<Idx,Idx> > todo;
244 std::set< std::pair<Idx,Idx> > done;
246 std::pair<Idx,Idx> currentstates, newstates;
247 StateSet::Iterator lit1, lit2;
257 FD_DF( "EmptyLanguageIntersection: push all combinations of initial states to todo:");
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);
269 FD_DF( "EmptyLanguageIntersection: processing reachable states:");
270 while (!todo.empty()) {
274 FD_WPC(done.size(),done.size()+todo.size(), "Product(): processing");
276 currentstates = todo.top();
278 done.insert(currentstates);
281 if(mark1. Exists(currentstates.first) && mark2. Exists(currentstates.second)) {
289 tit2_end = rGen2. TransRelEnd(currentstates.second);
290 while((tit1 != tit1_end) && (tit2 != tit2_end)) {
292 if(tit1->Ev == tit2->Ev) {
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);
304 else if (tit1->Ev < tit2->Ev) {
308 else if (tit1->Ev > tit2->Ev) {
318 Product(rGen1, rGen2, ProductGen);
320 if(empty != altempty) {
323 FD_ERR( "EmptyLanguageIntersection(): ERROR -- ref result: " << altempty);
334 << "," << rGen2. Name() << ")");
340 FD_DF( "Automaton("<< rGen. Name() << "," << rAlphabet. Name() << ")");
343 EventSet::Iterator eit;
344 StateSet::Iterator sit;
347 #ifdef FAUDES_CHECKED
349 FD_WARN( "Automaton(): nondeterministic parameter " << rGen. Name() << ".");
372 bool dumpReached= false;
404 for(;sit!=acc. End();++sit) {
405 FD_DF( "Automaton: processing state " << *sit);
409 if(tit->X1 >= cs) break;
412 if(tit->X1 == cs) found= true;
415 FD_DF( "Automaton: state not found, all transitions go to dump");
418 if(cs!=dump) dumpReached= true;
426 FD_DF( "Automaton: processing " << tit->Str() << " awaiting " << ce);
429 if(ce==tit->Ev) break;
431 FD_DF( "Automaton: add " << cs << "-(" << ce << ")->dump");
433 if(cs!=dump) dumpReached= true;
445 if(tit->X1!=cs) {fin= true; break;}
446 if(tit->Ev!=ce) break;
447 FD_DF( "Automaton: skip " << tit->Str());
457 FD_DF( "Automaton: fin " << cs << "-(" << *eit << ")->dump");
459 if(cs!=dump) dumpReached= true;
477 FD_DF( "Automaton("<< rGen. Name() << ", ...)");
484 FD_DF( "Automaton("<< rGen. Name() << ")");
485 std::string name=rGen. Name();
493 FD_DF( "LanguageComplement("<< rGen. Name() << "," << rAlphabet. Name() << ")");
496 std::string name = rGen. Name();
514 FD_DF( "LanguageComplement("<< rGen. Name() << ")");
515 std::string name=rGen. Name();
543 FD_DF( "LanguageDifference("<< rGen1. Name() << "," << rGen2. Name() << ")");
554 if(&rResGen == &rGen1 || &rResGen== &rGen2) {
555 pResGen = rResGen. New();
559 #ifdef FAUDES_CHECKED
561 std::stringstream errstr;
562 errstr << "Nondeterministic parameter " << rGen2. Name() << ".";
563 throw Exception( "LanguageDifference()", errstr.str(), 101);
577 FD_DF( "LanguageDifference(...): stage 2");
580 if(pResGen != &rResGen) {
581 pResGen-> Move(rResGen);
585 FD_DF( "LanguageDifference(...): done");
592 FD_DF( "LanguageConcatenateNonDet(" << rGen1. Name() << "," << rGen2. Name() << ")");
599 if(&rResGen== &rGen1 || &rResGen== &rGen2) {
600 pResGen= rResGen. New();
610 std::map<Idx,Idx> Gen1StatesMap;
611 std::map<Idx,Idx> Gen2StatesMap;
614 StateSet::Iterator sit;
619 if (stateNamesEnabled) {
622 Gen1StatesMap[*sit] = pResGen-> InsState();
626 if (stateNamesEnabled) {
629 Gen2StatesMap[*sit] = pResGen-> InsState();
635 pResGen-> SetTransition(Gen1StatesMap[tit->X1], tit->Ev, Gen1StatesMap[tit->X2]);
639 pResGen-> SetTransition(Gen2StatesMap[tit->X1], tit->Ev, Gen2StatesMap[tit->X2]);
653 bool concatenateEpsilon1= false;
656 concatenateEpsilon1= true;
666 if(concatenateEpsilon1)
674 pResGen-> SetTransition(Gen1StatesMap[tit->X1], tit->Ev, Gen2StatesMap[*sit]);
683 pResGen-> Name( "ConcatenateNonDet("+rGen1. Name()+ ","+rGen2. Name()+ ")");
686 if(pResGen != &rResGen) {
687 pResGen-> Move(rResGen);
697 FD_DF( "LanguageConcatenate("<< rGen1. Name()
698 << "," << rGen2. Name() << ")");
709 rResGen. Name( "Concatenate("+rGen1. Name()+ ","+rGen2. Name()+ ")");
717 << "," << rResGen. Name() << ")");
724 EventSet::Iterator evit;
738 for (evit = rAlphabet. Begin(); evit != rAlphabet. End(); ++evit) {
743 rResGen. Name( "FullLanguage("+rAlphabet. Name()+ ")");
750 FD_DF( "AlphabetLanguage("<< rAlphabet. Name()
751 << "," << rResGen. Name() << ")");
757 rResGen. Name( "AlphabetLanguage("+rAlphabet. Name()+ ")");
760 if(rAlphabet. Empty()){
761 FD_WARN( "AlphabetLanguage: empty alphabet.");
767 EventSet::Iterator evit;
783 for (evit = rAlphabet. Begin(); evit != rAlphabet. End(); ++evit) {
792 FD_DF( "EmptyStringLanguage("<< rAlphabet. Name()
793 << "," << rResGen. Name() << ")");
814 rResGen. Name( "EmptyStringLanguage("+rAlphabet. Name()+ ")");
821 FD_DF( "EmptyStringLanguage("<< rAlphabet. Name()
822 << "," << rResGen. Name() << ")");
831 rResGen. Name( "EmptyLanguage("+rAlphabet. Name()+ ")");
848 FD_DF( "LanguageInclusion("<< rGen1. Name() << "," << rGen2. Name() << ")");
862 FD_DF( "LanguageEquality("<< rGen1. Name() << "," << rGen2. Name() << ")");
871 FD_DF( "KleeneClosure("<< rGen. Name() << ")");
894 FD_DF( "KleeneClosure("<< rGen. Name() << ", ... )");
897 if(&rGen==&rResGen) {
925 FD_DF( "KleeneClosureNonDet("<< rGen. Name() << ")");
949 Idx imstate = istate;
954 TransToInsert. Insert(imstate, tit->Ev, tit->X2);
956 for (tit = TransToInsert. Begin(); tit != TransToInsert. End(); ++tit) {
959 TransToInsert. Clear();
970 TransToInsert. Insert(tit->X1, tit->Ev, imstate);
974 for (tit = TransToInsert. Begin(); tit != TransToInsert. End(); ++tit) {
983 FD_DF( "PrefixClosure("<< rGen. Name() << ")");
1036 FD_DF( "SelfLoop(" << rGen. Name() << "," << rAlphabet. Name() << ")");
1044 EventSet::Iterator evit,evbegin,evend;
1045 evbegin = rAlphabet. Begin();
1046 evend = rAlphabet. End();
1047 StateSet::Iterator sit;
1051 for(evit = evbegin; evit != evend; ++evit){
1063 FD_DF( "SelfLoopMarkedStates(" << rGen. Name() << "," << rAlphabet. Name() << ")");
1067 + "," + rAlphabet. Name() + ")");
1073 EventSet::Iterator evit,evbegin,evend;
1074 evbegin = rAlphabet. Begin();
1075 evend = rAlphabet. End();
1076 StateSet::Iterator sit;
1080 for(evit = evbegin; evit != evend; ++evit){
1092 FD_DF( "SelfLoop(" << rGen. Name() << "," << rAlphabet. Name() << "," << rStates. Name() << ")");
1096 + "," + rAlphabet. Name() + "," + rStates. Name() + ")");
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);
1112 EventSet::Iterator evit,evbegin,evend;
1113 evbegin = rAlphabet. Begin();
1114 evend = rAlphabet. End();
1115 StateSet::Iterator sit;
1118 for (sit = rStates. Begin(); sit != rStates. End(); ++sit) {
1119 for(evit = evbegin; evit != evend; ++evit){
1130 FD_WARN( "IsPrefixClosed(): API depreciated, use IsClosed()");
#define FD_WPC(cntnow, contdone, message)
const std::string & Name(void) const
std::vector< int >::size_type Position
virtual const T & At(const Position &pos) const
Iterator Begin(void) const
bool Insert(const Transition &rTransition)
TBaseSet< Transition, TransSort::X1EvX2 >::Iterator Iterator
void Write(const Type *pContext=0) 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
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
bool ExistsMarkedState(Idx index) const
std::string UniqueStateName(const std::string &rName) const
const StateSet & States(void) const
void InjectAlphabet(const EventSet &rNewalphabet)
bool Exists(const T &rElem) const
Iterator Begin(void) const
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)
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)
bool IsNonblocking(const GeneratorVector &rGvec)
bool IsPrefixClosed(const Generator &rGen)
std::string CollapsString(const std::string &rString, unsigned int len)
libFAUDES 2.33l
--- 2025.09.16
--- c++ api documentaion by doxygen
|