cfl_regular.h
Go to the documentation of this file.
1 
2 /** @file cfl_regular.h
3 
4 Operations on regular languages.
5 See [Cassandras and Lafortune. Introduction to Discrete Event Systems] for an
6 introduction to regular language operations.
7 Operations are always performed on language(s) marked by the passed generator(s),
8 resulting in the language(s) marked by the resulting generator(s).
9 Only if mentioned extra, the same is done for the involved generated (prefix-closed)
10 languages.
11 
12 */
13 
14 /* FAU Discrete Event Systems Library (libfaudes)
15 
16  Copyright (C) 2006 Bernd Opitz
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 #ifndef FAUDES_REGULAR_H
35 #define FAUDES_REGULAR_H
36 
37 #include "cfl_definitions.h"
38 #include "cfl_parallel.h"
39 #include "cfl_project.h"
40 
41 namespace faudes {
42 
43 /**
44  * Language union, nondeterministic version.
45  *
46  * This function performs the union of two languages marked by two generators;
47  * the resulting generator marks the resulting language.
48  * Moreover, the same is done for the involved generated (prefix-closed) languages.
49  * Method:
50  * This function implements the textbook version in taking unions of all generator
51  * entities (alphabets, initial states, ...) of rGen1 and rGen2. State sets are taken
52  * as disjoint by definition and thus reindexed and renamed to achieve disjoint union.
53  * The resulting language is defined over the union of the alphabets of the original
54  * languages; original languages defined over different alphabets are treated as if
55  * they were defined over the union of both alphabets.
56  *
57  * Determinism:
58  * Input parameters may be nondeterministic.
59  * This function is more economical than the deterministic version, but likely to
60  * produce a non-deterministic result; see also LanguageUnion().
61  *
62  * No restrictions on parameters.
63  *
64  * @param rGen1
65  * generator generating/marking L1/Lm1
66  * @param rGen2
67  * generator generating/marking L2/Lm2
68  * @param rResGen
69  * resulting generator generating/marking the language union of L1 and L2/of Lm1 and Lm2
70  *
71  *
72  * @ingroup GeneratorFunctions
73  */
74 extern FAUDES_API void LanguageUnionNonDet(const Generator& rGen1, const Generator& rGen2,
75  Generator& rResGen);
76 
77 /**
78  * Language union, deterministic version.
79  *
80  * This function performs the union of two languages marked by two generators;
81  * the resulting generator marks the resulting language.
82  * Moreover, the same is done for the involved generated (prefix-closed) |languages.
83  * Method:
84  * This function implements the textbook version (which textbook??) in taking unions
85  * of all generator entities (alphabets, initial states, ...). State sets are taken
86  * as disjoint by definition and thus reindexed and renamed to achieve disjoint union.
87  * The resulting language is defined over the union of the alphabets of the original
88  * languages.
89  *
90  * Determinism:
91  * Input parameters may be nondeterministic.
92  * This function calls LanguageUnionNonDet() and then Deterministic() to convert the
93  * result into a deterministic generator. Note that this conversion is usually
94  * straightforward, but there exist theoretical worst-case examples of exponential complexity.
95  *
96  * No restrictions on parameters.
97  *
98  * ToDo: a version similar to parallel composition that produces a deterministic result by construction. (?)
99  *
100  * @param rGen1
101  * generator generating/marking L1/Lm1
102  * @param rGen2
103  * generator generating/marking L2/Lm2
104  * @param rResGen
105  * resulting generator generating/marking the language union of L1 and L2/of Lm1 and Lm2
106  *
107  * <h4>Example:</h4>
108  * <table border=0> <tr> <td> <table>
109  * <tr> <td> Generator G1 </td> <td> Generator G2 </td> </tr>
110  * <tr>
111  * <td> @image html tmp_boolean_g1.png </td>
112  * <td> @image html tmp_boolean_g2.png </td>
113  * </tr>
114  * </table> </td> </tr> <tr> <td> <table width=100%>
115  * <tr> <td> LanguageUnion(G1,G2,Result) </td> </tr>
116  * <tr> <td> @image html tmp_union_g1g2.png </td> </tr>
117  * </table> </td> </tr> </table>
118  *
119  * @ingroup GeneratorFunctions
120  */
121 extern FAUDES_API void LanguageUnion(const Generator& rGen1, const Generator& rGen2,
122  Generator& rResGen);
123 
124 /**
125  * Language union.
126  *
127  * See also LanguageUnion(const Generator&, const Generator&, Generator&);
128  * This version takes a vector of generators as argument to perform
129  * the union for multiple languages. The implementation
130  * calls the std union multiple times, future implementations may
131  * do better.
132  *
133  * @param rGenVec
134  * Vector of input generators
135  * @param rResGen
136  * Reference to resulting generator
137  *
138  */
139 extern FAUDES_API void LanguageUnion(const GeneratorVector& rGenVec, Generator& rResGen);
140 
141 
142 /**
143  * Language intersection.
144  *
145  * This function performs the intersection of two languages marked by two generators;
146  * the resulting generator marks the resulting language.
147  * Moreover, the same is done for the involved generated (prefix-closed) languages.
148  * The resulting languages are defined over the intersection of the involved alphabets.
149  * Method:
150  * This function calls Product(). In the product of two automata, an event occurs if
151  * and only if it occurs in both automata rGen1 and rGen2. The result generates/marks
152  * the intersection of the involved languages, see e.g.
153  * [Cassandras, Lafortune. Introduction to Discrete Event Systems, p.84]
154  *
155  * Determinism:
156  * Input parameters may be nondeterministic.
157  * Result can be nondeterministic only if input parameters are nondeterministic.
158  *
159  * No restrictions on parameters.
160  *
161  * @param rGen1
162  * generator generating/marking L1/Lm1
163  * @param rGen2
164  * generator generating/marking L2/Lm2
165  * @param rResGen
166  * resulting generator generating/marking the language intersection of L1 and L2/of Lm1 and Lm2
167  *
168  * <h4>Example:</h4>
169  *
170  * <table border=0> <tr> <td> <table>
171  * <tr> <td> Generator G1 </td> <td> Generator G2 </td> </tr>
172  * <tr>
173  * <td> @image html tmp_boolean_g1.png </td>
174  * <td> @image html tmp_boolean_g2.png </td>
175  * </tr>
176  * </table> </td> </tr> <tr> <td> <table width=100%>
177  * <tr> <td> LanguageIntersection(G1,G2,Result) </td> </tr>
178  * <tr> <td> @image html tmp_intersection_g1g2.png </td> </tr>
179  * </table> </td> </tr> </table>
180  *
181  * @ingroup GeneratorFunctions
182  */
183 extern FAUDES_API void LanguageIntersection(const Generator& rGen1, const Generator& rGen2,
184  Generator& rResGen);
185 
186 /**
187  * Language intersection.
188  *
189  * See also LanguageUnion(const Generator&, const Generator&, Generator&);
190  * This version takes a vector of generators as argument to perform
191  * the intersection for multiple languages. The implementation
192  * calls the std intersection multiple times, future implementations may
193  * do better.
194  *
195  * @param rGenVec
196  * Vector of input generators
197  * @param rResGen
198  * Reference to resulting generator
199  *
200  */
201 extern FAUDES_API void LanguageIntersection(const GeneratorVector& rGenVec, Generator& rResGen);
202 
203 
204 /**
205  * Test for empty language intersection (same as Disjoind()).
206  *
207  * This function checks if the intersection of two languages marked by two generators
208  * is empty that is the two languages are disjoint.
209  * The involved generated (prefix-closed) languages are not considered. This function
210  * is identical to Disjoint().
211  *
212  * No restrictions on parameters.
213  *
214  * @param rGen1
215  * generator marking Lm1
216  * @param rGen2
217  * generator marking Lm2
218  *
219  * @return
220  * true if language intersection is empty, false if not.
221  *
222  * @ingroup GeneratorFunctions
223  */
224 extern FAUDES_API bool EmptyLanguageIntersection(const Generator& rGen1, const Generator& rGen2);
225 
226 /**
227  * Test whether two languages are disjoint.
228  *
229  * This function tests whether the intersection of two languages marked by two generators
230  * is empty, ie the two languages are disjoint.
231  * The involved generated (prefix-closed) languages are not considered. This function
232  * is identical to EmptyLanguageIntersection().
233  *
234  * No restrictions on parameters.
235  *
236  * @param rGen1
237  * generator marking Lm1
238  * @param rGen2
239  * generator marking Lm2
240  *
241  * @return
242  * true if language intersection is empty, false if not.
243  *
244  * @ingroup GeneratorFunctions
245  */
246 extern FAUDES_API bool LanguageDisjoint(const Generator& rGen1, const Generator& rGen2);
247 
248 /**
249  * Convert generator to automaton.
250  *
251  * Convert a generator accepting the language Lm into a formal automaton recognizing Lm
252  * with a dump state representing L-Sigma^*. In this function, Sigma is given by the
253  * alphabet of rGen; see also Automaton(rGen,rAlphabet).
254  *
255  * Note: An automaton is a deterministic transition structure according to the formal
256  * definition; see also "Determinism" below.
257  *
258  * Note: pre libFAIDES v2.33 we trimmed the automaton since non-coaccessible states
259  * wont contribute to Lm. This was dropped to be tolerant to alternative acceptance
260  * conditions. Preprocess with Trim explicitly to obtain pre v2.33 semantics.
261  *
262  * Method:
263  * Unaccessible states are erased, as they do not contribute to the languages generated
264  * or accepted by rGen. A dump state representing "L-Sigma*" is created. Then, the
265  * transition relation is completed such that it is fully defined for each state and
266  * each event. Formerly undefined transitions lead to the dump state.
267  *
268  * Determinism:
269  * Input parameter has to be deterministic for correct result. If not, then the
270  * (also nondeterministic) result recognizes the correct language, but the dump state
271  * does not represent "Sigma*-PrefixClosure(Lm)" as it should; see also
272  * example ExAutomaton_basic(). If FAUDES_CHECKED is defined a warning on non-deterministic
273  * input is issued.
274  *
275  * No further restrictions on parameter.
276  *
277  * @param rGen
278  * generator that is converted to automaton
279  * @return
280  * index of dumpstate (0 for none)
281  *
282  * <h4>Example:</h4>
283  * <table>
284  * <tr> <td> Generator G </td> <td> Automaton(G) </td> </tr>
285  * <tr>
286  * <td> @image html tmp_automaton_g.png </td>
287  * <td> @image html tmp_automaton_gRes.png </td>
288  * </tr>
289  * </table>
290  *
291  * @ingroup GeneratorFunctions
292  */
293 extern FAUDES_API Idx Automaton(Generator& rGen);
294 
295 /**
296  * Convert generator to automaton.
297  *
298  * This is an API wrapper for Automaton(rGen,rGen).
299  *
300  * @param rGen
301  * input generator
302  * @param rRes
303  * converted automaton
304  * @return
305  * index of dumpstate (0 for none)
306  */
307 extern FAUDES_API Idx Automaton(const Generator& rGen, Generator& rRes);
308 
309 /**
310  * Convert generator to automaton wrt specified alphabet.
311  *
312  * Convert a generator accepting the language Lm into a formal automaton recognizing Lm
313  * with a dump state representing L-Sigma^*. In this function, Sigma is specified explixitly.
314  *
315  * @param rGen
316  * generator that is converted to automaton
317  * @param rAlphabet
318  * the dump state of the resulting automaton represents the
319  * language L_dump=rAlphabet*-L
320  * @return
321  * index of dumpstate (0 for none)
322  *
323  * @ingroup GeneratorFunctions
324  */
325 extern FAUDES_API Idx Automaton(Generator& rGen, const EventSet& rAlphabet);
326 
327 /**
328  * Language complement.
329  *
330  * Convert generator marking the language Lm into generator marking the language
331  * complement of Lm which is defined as Sigma*-Lm. In this function, Sigma is
332  * given by the alphabet of rGen; see also LanguageComplement(rGen,rAlphabet).
333  * The original generated language is ignored.
334  * Method:
335  * This function calls Automaton() first and then inverts the marking of the states
336  * of the result.
337  *
338  * Determinism:
339  * Input parameter has to be deterministic for correct result, see Automaton() for
340  * explanations.
341  * If FAUDES_CHECKED is defined a warning on non-deterministic input is issued.
342  * (by function Automaton()).
343  *
344  * No further restrictions on parameter.
345  *
346  * @param rGen
347  * generator on which the language complement is performed
348  *
349  * <h4>Example:</h4>
350  * <table>
351  * <tr> <td> Generator G </td> <td> LanguageComplement(G) </td> </tr>
352  * <tr>
353  * <td> @image html tmp_boolean_g1.png </td>
354  * <td> @image html tmp_complement_g1.png </td>
355  * </tr>
356  * </table>
357  *
358  *
359  * @ingroup GeneratorFunctions
360  */
361 extern FAUDES_API void LanguageComplement(Generator& rGen);
362 
363 /**
364  * Language complement wrt specified alphabet.
365  *
366  * Convert generator marking the language Lm into generator marking the language
367  * complement of Lm which is defined as Sigma*-Lm. In this function, Sigma is
368  * given by the parameter rAlphabet.
369  * The original generated language is ignored.
370  * Method:
371  * This function calls Automaton() first and then inverts the marking of the states
372  * of the result.
373  *
374  * Determinism:
375  * Input parameter has to be deterministic for correct result, see Automaton() for
376  * explanations.
377  * If FAUDES_CHECKED is defined a warning on non-deterministic input is issued.
378  * (by function Automaton()).
379  *
380  * No further restrictions on parameter.
381  *
382  * @param rGen
383  * generator on which the language complement is performed
384  *
385  * @param rAlphabet
386  * reference alphabet to build the complement
387  *
388  * @ingroup GeneratorFunctions
389  */
390 extern FAUDES_API void LanguageComplement(Generator& rGen, const EventSet& rAlphabet);
391 
392 
393 /**
394  * Language Complement (uniform API wrapper).
395  *
396  * @param rGen
397  * generator on which the language complement is performed
398  *
399  * @param rRes
400  * resulting generator
401  *
402  * @ingroup GeneratorFunctions
403  */
404 extern FAUDES_API void LanguageComplement(const Generator& rGen, Generator& rRes);
405 
406 /**
407  * Language Complement (uniform API wrapper).
408  *
409  * @param rGen
410  * generator on which the language complement is performed
411  *
412  * @param rSigma
413  * reference alphabet to build the complement
414  *
415  * @param rRes
416  * resulting generator
417  *
418  * @ingroup GeneratorFunctions
419  */
420 extern FAUDES_API void LanguageComplement(const Generator& rGen, const EventSet& rSigma, Generator& rRes);
421 
422 
423 
424 /**
425  * Language difference (set-theoretic difference).
426  *
427  * This function calculates Lm1-Lm2 (sometimes also denoted by Lm1\\Lm2), that is the
428  * set of all strings included in Lm1 but not in Lm2.
429  * Method:
430  * The language difference is computed by taking the intersection of Lm1 with the
431  * complement of Lm2.
432  *
433  * Determinism:
434  * Due to the use of LanguageComplement(), rGen2 has to be deterministic.
435  * Result can be nondeterministic only if rGen1 is nondeterministic.
436  *
437  * Restrictions on prameters:
438  * rGen2 has to be deterministic.
439  *
440  * @param rGen1
441  * generator marking the language Lm1
442  * @param rGen2
443  * generator marking the language Lm2
444  * @param rResGen
445  * generator marking the language difference Lm1-Lm2
446  *
447  * @exception Exception
448  * - nondeterministic parameter rGen2 (id 101).
449  *
450  * <h4>Example:</h4>
451  * <table border=0> <tr> <td> <table>
452  * <tr> <td> Generator G1 </td> <td> Generator G2 </td> </tr>
453  * <tr>
454  * <td> @image html tmp_difference_g1.png </td>
455  * <td> @image html tmp_difference_g2.png </td>
456  * </tr>
457  * </table> </td> </tr> <tr> <td> <table width=100%>
458  * <tr> <td> LanguageDifference(G1,G2,Result) </td> </tr>
459  * <tr> <td> @image html tmp_difference_g1minusg2.png </td> </tr>
460  * </table> </td> </tr> </table>
461  *
462  * @ingroup GeneratorFunctions
463  */
464 extern FAUDES_API void LanguageDifference(const Generator& rGen1, const Generator& rGen2,
465  Generator& rResGen);
466 
467 /**
468  * Language concatenation, nondeterministic version.
469  *
470  * With the languages Lm1 and Lm2 marked by rGen1 and rGen2, respectively, the result
471  * rResGen marks the concatenation LmRes=Lm1Lm2.
472  * The languages generated by rGen1 and rGen2 are ignored. It would be possible to let
473  * the result also generate the concatenation of the generated languages; however, this can
474  * produce disproportionate computational overhead, if only the marked languages shall be
475  * concatenated.
476  * Method:
477  * rGen2 is appended to rGen1: first, the initial states of rGen2 are erased. Then,
478  * transitions, that formerly started from the initial state(s) of rGen2, are redirected
479  * and multiplied such that they start from each marked state of rGen1. The marked states
480  * corresponding to rGen2 remain marked. The marked states of rGen1 remain marked only if
481  * rGen2 has at least one marked initial state (i.e. if epsilon is concatenated to Lm1.)
482  *
483  * Determinism:
484  * Input parameters may be nondeterministic. Result can be nondeterministic even if input
485  * parameters are deterministic; see also LanguageConcatenate().
486  *
487  * No restrictions on parameters.
488  *
489  * @param rGen1
490  * generator marking Lm1
491  * @param rGen2
492  * generator marking Lm2
493  * @param rResGen
494  * resulting generator marking the language concatenation Lm1Lm2
495  *
496  * @ingroup GeneratorFunctions
497  */
498 extern FAUDES_API void LanguageConcatenateNonDet(const Generator& rGen1, const Generator& rGen2,
499  Generator& rResGen);
500 
501 /**
502  * Language concatenation, deterministic version.
503  *
504  * With the languages Lm1 and Lm2 marked by rGen1 and rGen2, respectively, the result
505  * rResGen marks the concatenation LmRes=Lm1Lm2.
506  * The languages generated by rGen1 and rGen2 are ignored. It would be possible to let
507  * the result also generate the concatenation of the generated languages; however, this can
508  * produce disproportionate computational overhead, if only the marked languages shall be
509  * concatenated.
510  * Method:
511  * rGen2 is appended to rGen1: first, the initial states of rGen2 are erased. Then,
512  * transitions, that formerly started from the initial state(s) of rGen2, are redirected
513  * and multiplied such that they start from each marked state of rGen1. The marked states
514  * corresponding to rGen2 remain marked. The marked states of rGen1 remain marked only if
515  * rGen2 has at least one marked initial state (i.e. if epsilon is concatenated to Lm1.)
516  *
517  * Determinism:
518  * Input parameters may be nondeterministic.
519  * This function calls LanguageUnionNonDet() and then Deterministic() to convert the
520  * result into a deterministic generator. Note that this conversion is usually
521  * straightforward, but there exist theoretical worst-case examples of exponential complexity.
522  *
523  * No restrictions on parameters.
524  *
525  * @param rGen1
526  * generator marking Lm1
527  * @param rGen2
528  * generator marking Lm2
529  * @param rResGen
530  * Resulting generator marking the language concatenation Lm1Lm2
531  *
532  * <h4>Example:</h4>
533  * <table border=0> <tr> <td> <table>
534  * <tr> <td> Generator G1 </td> <td> </td> <td> LanguageConcatenate(G1,G3,Result) </td> </tr>
535  * <tr>
536  * <td> @image html tmp_concat_g1.png </td>
537  * <td> </td>
538  * <td> @image html tmp_concat_g1g3.png </td>
539  * </tr>
540  * <tr> <td> Generator G2 </td> <td> </td> <td> LanguageConcatenate(G1,G4,Result) </td> </tr>
541  * <tr>
542  * <td> @image html tmp_concat_g2.png </td>
543  * <td> </td>
544  * <td> @image html tmp_concat_g1g4.png </td>
545  * </tr>
546  * </tr>
547  * <tr> <td> Generator G3 </td> <td> </td> <td> LanguageConcatenate(G2,G3,Result) </td> </tr>
548  * <tr>
549  * <td> @image html tmp_concat_g3.png </td>
550  * <td> </td>
551  * <td> @image html tmp_concat_g2g3.png </td>
552  * </tr>
553  * </tr>
554  * <tr> <td> Generator G4 </td> <td> </td> <td> LanguageConcatenate(G2,G4,Result) </td> </tr>
555  * <tr>
556  * <td> @image html tmp_concat_g4.png </td>
557  * <td> </td>
558  * <td> @image html tmp_concat_g2g4.png </td>
559  * </tr>
560  * </table> </td> </tr> </table>
561  *
562  * @ingroup GeneratorFunctions
563  */
564 extern FAUDES_API void LanguageConcatenate(const Generator& rGen1, const Generator& rGen2,
565  Generator& rResGen);
566 
567 /**
568  * Full Language, L(G)=Lm(G)=Sigma*.
569  *
570  * Construct generator generating and marking full language Sigma* from alphabet Sigma.
571  * Method: this function creates a generator with one state that is marked and init state. This
572  * state is selflooped with all events from rAlphabet.
573  *
574  * @param rAlphabet
575  * Alphabet Sigma from which full language Sigma* is built
576  * @param rResGen
577  * Generator generating and marking full language Sigma*
578  *
579  * <h4>Example:</h4>
580  * <table>
581  * <tr> <td> FullLanguage(Sigma={a,b},Result) </td> </tr>
582  * <tr>
583  * <td> @image html tmp_languagesFull_result.png </td>
584  * </tr>
585  * </table>
586  *
587  * @ingroup GeneratorFunctions
588  */
589 extern FAUDES_API void FullLanguage(const EventSet& rAlphabet, Generator& rResGen);
590 
591 /**
592  * Alphabet Language, L(G)=Lm(G)=Sigma
593  *
594  * Construct generator generating and marking an alphabet as languages, that is L(G)=Lm(G)=Sigma.
595  * Method: this function creates a generator with one init state and one marked state. For each
596  * event from rAlphabet, a transition is inserted leading from the init state to the marked state.
597  *
598  * No restrictions on parameters.
599  *
600  * @param rAlphabet
601  * alphabet from which alphabet language is built
602  * @param rResGen
603  * generator with languages Lm(G)=Sigma
604  *
605  * <h4>Example:</h4>
606  * <table>
607  * <tr> <td> AlphabetLanguage(Sigma={a,b},Result) </td> </tr>
608  * <tr>
609  * <td> @image html tmp_languagesAlphabet_result.png </td>
610  * </tr>
611  * </table>
612  *
613  * @ingroup GeneratorFunctions
614  */
615 extern FAUDES_API void AlphabetLanguage(const EventSet& rAlphabet, Generator& rResGen);
616 
617 /**
618  * Empty string language, L(G)=Lm(G)={epsilon}.
619  *
620  * Construct generator generating and marking the empty string, that is L(G)=Lm(G)={epsilon}.
621  * Method: this function creates a generator with one marked init state and the alphabet rAlphabet.
622  *
623  * No restrictions on parameters.
624  *
625  * @param rAlphabet
626  * alphabet of the resulting generator
627  * @param rResGen
628  * generator with languages L(G)=Lm(G)={epsilon} and alphabet rAlphabet
629  *
630  * <h4>Example:</h4>
631  * <table>
632  * <tr> <td> EmptyStringLanguage(Sigma={a,b},Result) </td> </tr>
633  * <tr>
634  * <td> @image html tmp_languagesEmptyString_result.png </td>
635  * </tr>
636  * </table>
637  *
638  * @ingroup GeneratorFunctions
639  */
640 extern FAUDES_API void EmptyStringLanguage(const EventSet& rAlphabet, Generator& rResGen);
641 
642 /**
643  * Empty language Lm(G)={}.
644  *
645  * Construct generator and marking the empty language, that is Lm(G)={}.
646  * Method: this function creates a deterministic generator with one initial state that is not marked.
647  * The alphabet is set as specified.
648  *
649  * No restrictions on parameters.
650  *
651  * @param rAlphabet
652  * Alphabet of the resulting generator
653  * @param rResGen
654  * Generator with language Lm(G)={}
655  *
656  * @ingroup GeneratorFunctions
657  */
658 extern FAUDES_API void EmptyLanguage(const EventSet& rAlphabet, Generator& rResGen);
659 
660 /**
661  * Test for Empty language Lm(G)=={}.
662  *
663  * Tests if the language marked by rGen is empty, that is if Lm(G)=={}. The generated
664  * language L(G) is not considered.
665  * Method:
666  * This function tests if
667  * a) the set of marked states is empty or else
668  * b) the intersection of the set of accessible states and the set of marked states
669  * is empty, i.e. if there is no marked state or if no marked state is accessible (reachable).
670  *
671  * No restrictions on parameter.
672  *
673  * @param rGen
674  * generator to be tested for empty marked language
675  *
676  * @return
677  * true on empty marked language, false on nonempty marked language
678  *
679  * @ingroup GeneratorFunctions
680  */
681 extern FAUDES_API bool IsEmptyLanguage(const Generator& rGen);
682 
683 /**
684  * Test language inclusion, Lm1<=Lm2.
685  *
686  * Test if language Lm1 marked by rGen1 is included in language Lm2 marked by rGen2. The
687  * generated languages are not considered.
688  * Method:
689  * This function checks if there is no string in Lm1 that is not in Lm2 by testing if
690  * the intersection of Lm1 and the language complement of Lm2 is empty.
691  *
692  * Restrictions on parameters: rGen2 has to be deterministic!
693  * If FAUDES_CHECKED is defined a warning on non-deterministic input is issued.
694  * (by function Automaton()).
695  *
696  * Determinism: correctness in case of nondeterministic parameter rGen1 has been tested with an
697  * example (see ExInclusion_simple), but not proven.
698  *
699  * ToDo: implement faster version using a variant of Product():
700  * compute product without storing result, return false as soon as some event is
701  * possible in Lm2 but not in Lm1.
702  *
703  * @param rGen1
704  * generator marking Lm1
705  * @param rGen2
706  * generator marking Lm2
707  *
708  * @return
709  * true if language marked by rGen1 is included in language marked by rGen2
710  *
711  * @ingroup GeneratorFunctions
712  */
713 extern FAUDES_API bool LanguageInclusion(const Generator& rGen1, const Generator& rGen2);
714 
715 /**
716  * Language equality, Lm1==Lm2.
717  *
718  * Test if the language Lm1 marked by rGen1 equals the language Lm2 marked by rGen2. The
719  * generated languages are not considered.
720  * Method:
721  * This function checks mutual inclusion of Lm1 in Lm2 and of Lm2 in Lm1 using the
722  * function LanguageInclusion().
723  *
724  * Restrictions on parameters: rGen1 and rGen2 have to be deterministic!
725  * If FAUDES_CHECKED is defined a warning on non-deterministic input is issued.
726  * (by function Automaton()).
727  *
728  * ToDo: implement faster, version using a variant of Product():
729  * compute product without storing result, return false as soon as rGen1 and rGen2
730  * "disagree" on the occurrence of some event.
731  *
732  * @param rGen1
733  * generator marking Lm1
734  * @param rGen2
735  * generator marking Lm2
736  *
737  * @return
738  * true if the language marked by rGen1 equals the language marked by rGen2
739  *
740  * @ingroup GeneratorFunctions
741  */
742 extern FAUDES_API bool LanguageEquality(const Generator& rGen1, const Generator& rGen2);
743 
744 /**
745  * Kleene Closure.
746  *
747  * This function computes the Kleene Closure ( ()* - operator) of the
748  * language marked by rGen. The generated language is not considered.
749  * Method: KleeneClosureNonDet() is called, which, for all transitions
750  * leading from a state x to a marked state, inserts a transition with the
751  * same event starting from x and leading to (one of) the initial state(s).
752  * As this step causes nondeterminism, the function Deterministic() is called.
753  * See also KleeneClosureNonDet().
754  *
755  * No restrictions on parameter.
756  *
757  * @param rGen
758  * generator marking the language Lm to which the Kleene Closure is applied
759  *
760  * <h4>Example:</h4>
761  * <table>
762  * <tr> <td> Generator G </td> <td> KleeneClosure(G) </td> </tr>
763  * <tr>
764  * <td> @image html tmp_kleene_g.png </td>
765  * <td> @image html tmp_kleene_gRes.png </td>
766  * </tr>
767  * </table>
768  *
769  * @ingroup GeneratorFunctions
770  */
771 extern FAUDES_API void KleeneClosure(Generator& rGen);
772 
773 /**
774  * Kleene Closure.
775  *
776  * This function is a convenience wrapper for KleeneClosure(Generator&).
777  *
778  *
779  * @ingroup GeneratorFunctions
780  */
781 extern FAUDES_API void KleeneClosure(const Generator& rGen, Generator& rResGen);
782 
783 /**
784  * Kleene Closure, nondeterministic version.
785  *
786  * This function computes the Kleene Closure ( ()* - operator) of the
787  * language marked by rGen. The generated language is not considered.
788  * Method: KleeneClosureNonDet() is called, which, for all transitions
789  * leading from a state x to a marked state, inserts a transition with the
790  * same event starting from x and leading to (one of) the initial state(s).
791  *
792  * @param rGen
793  * generator marking the language Lm to which Kleene Closure is applied
794  *
795  * @ingroup GeneratorFunctions
796  */
797 extern FAUDES_API void KleeneClosureNonDet(Generator& rGen);
798 
799 /**
800  * Prefix Closure.
801  *
802  * This function computes the prefix closure the language Lm marked by rGen. A
803  * language Lm is prefix closed if each string of Lm implies that all its
804  * prefixes are also element of Lm. The prefix closure of a language marked by
805  * a generator is always a subset of the generated language and is represented
806  * by the set of coaccessible states of the generator.
807  * Method:
808  * First, Coaccessible() is called to erase all states of rGen that do not
809  * represent prefixes of marked strings. Then, all remaining states are marked.
810  *
811  * No restrictions on parameter.
812  *
813  * ToDo: (slightly) more efficient version: implement generator function
814  * CoAccessibleSet() similar to AccessibleSet() and call
815  * InjectMarkedStates(AccessibleSet()).
816  *
817  * @param rGen
818  * generator marking the language Lm to which prefix closure is applied
819  *
820  * <h4>Example:</h4>
821  * <table>
822  * <tr> <td> Generator G </td> <td> PrefixClosure(G) </td> </tr>
823  * <tr>
824  * <td> @image html tmp_prefixclosure_g.png </td>
825  * <td> @image html tmp_prefixclosure_gRes.png </td>
826  * </tr>
827  * </table>
828  *
829  * @ingroup GeneratorFunctions
830  */
831 extern FAUDES_API void PrefixClosure(Generator& rGen);
832 
833 
834 /**
835  * Test for prefix closed marked language.
836  *
837  * This function tests whether the language Lm(G) marked by the specified generator G
838  * is prefix closed. It does so by testing whether all accessible and coaccessible
839  * states are marked.
840  *
841  * The specified generator must be deterministic.
842  *
843  * @param rGen
844  * generator G marking the Lm(G) to test
845  * @return
846  * True <> Lm(G) is prefix closed
847  *
848  * @ingroup GeneratorFunctions
849  */
850 extern FAUDES_API bool IsClosed(const Generator& rGen);
851 
852 
853 /**
854  * Test for nonblocking generator
855  *
856  * A generator G is nonblocking if closure(Lm(G)) = L(G), i.e.
857  * if every accessible state is coacessile.
858  *
859  * The specified generator must be deterministic.
860  *
861  * @param rGen
862  * generator G marking to test
863  * @return
864  * True <> G is nonblocking
865  *
866  * @ingroup GeneratorFunctions
867  */
868 extern FAUDES_API bool IsNonblocking(const Generator& rGen);
869 
870 /**
871  * Test for nonblocking marked languages.
872  *
873  * Two languages L1 and L2 are nonblocking, if
874  * closure(L1 || L2) == closure(L1) || closure(L2).
875  *
876  * This function performs the parallel composition of the two
877  * specified generators and tests it for nonblockingness. Provided
878  * that both generators are trim, this is equivalent to the
879  * respective marked languages being nonblocking.
880  *
881  * The specified generators must be trim.
882  *
883  * @param rGen1
884  * Generator G1
885  * @param rGen2
886  * Generator G2
887  * @return
888  * True <> Lm(G1) and Lm(G2) are nonblocking
889  *
890  * @ingroup GeneratorFunctions
891  */
892 extern FAUDES_API bool IsNonblocking(const Generator& rGen1, const Generator& rGen2);
893 
894 
895 /**
896  * Self-loop all states.
897  *
898  * This function selfoops all states of rGen with the events from rAlphabet.
899  * Method:
900  * The alphabet of rGen is extended by rAlphabet. For each state x of rGen
901  * and each event alpha of rAlphabet, a transition (x,alpha,x) is inserted,
902  * irrespective of whether this event was already active in x before.
903  * See also SelfLoop(rGen,rAlphabet,rStates) and SelfLoopMarkedStates(rGen,rAlphabet).
904  *
905  * No restrictions on parameter.
906  *
907  * Determinism: resulting generator is nondeterministic, if it was nondeterministic
908  * before, or if rGen already contains one or more (non selfloop) transitions with
909  * events from rAlphabet.
910  *
911  * @param rGen
912  * generator to be selflooped with events from rAlphabet
913  * @param rAlphabet
914  * alphabet with selfloop events
915  *
916  * <h4>Example:</h4>
917  * <table>
918  * <tr> <td> Generator G </td> <td> SelfLoop(G,Sigma={e,f}) </td> </tr>
919  * <tr>
920  * <td> @image html tmp_selfloop_g.png </td>
921  * <td> @image html tmp_selfloop_gRes.png </td>
922  * </tr>
923  * </table>
924  *
925  * @ingroup GeneratorFunctions
926  */
927 extern FAUDES_API void SelfLoop(Generator& rGen,const EventSet& rAlphabet);
928 
929 /**
930  * Self-loop all marked states.
931  *
932  * This function selfoops all marked states of rGen with the events from rAlphabet.
933  * Method:
934  * The alphabet of rGen is extended by rAlphabet. For each marked state x of rGen
935  * and each event alpha of rAlphabet, a transition (x,alpha,x) is inserted,
936  * irrespective of whether this event was already active in x before.
937  * See also SelfLoop(rGen,rAlphabet) and SelfLoop(rGen,rAlphabet,rStates).
938  *
939  * No restrictions on parameter.
940  *
941  * Determinism: resulting generator is nondeterministic, if it was nondeterministic
942  * before, or if rGen already contains one or more (non selfloop) transitions
943  * starting from a marked state with events from rAlphabet.
944  *
945  * @param rGen
946  * generator with marked states to be selflooped with events from rAlphabet
947  * @param rAlphabet
948  * alphabet with selfloop events
949  *
950  * <h4>Example:</h4>
951  * <table>
952  * <tr> <td> Generator G </td> <td> SelfLoopMarkedStates(G,Sigma={e,f}) </td> </tr>
953  * <tr>
954  * <td> @image html tmp_selfloop_g.png </td>
955  * <td> @image html tmp_selfloopMarked_gRes.png </td>
956  * </tr>
957  * </table>
958  *
959  * @ingroup GeneratorFunctions
960  */
961 extern FAUDES_API void SelfLoopMarkedStates(Generator& rGen,const EventSet& rAlphabet);
962 
963 /**
964  * Self-loop specified states.
965  *
966  * This function selfoops the states rStates of rGen with the events from rAlphabet.
967  * Method:
968  * The alphabet of rGen is extended by rAlphabet. For each state x of rStates
969  * and each event alpha of rAlphabet, a transition (x,alpha,x) is inserted,
970  * irrespective of whether this event was already active in x before.
971  * See also SelfLoop(rGen,rAlphabet) and SelfLoopMarkedStates(rGen,rAlphabet).
972  *
973  * No restrictions on parameter.
974  *
975  * Determinism: resulting generator is nondeterministic, if it was nondeterministic
976  * before, or if rGen already contains one or more (non selfloop) transitions
977  * starting from a state of rState with events from rAlphabet.
978  *
979  * @param rGen
980  * generator with marked states to be selflooped with events from rAlphabet
981  * @param rAlphabet
982  * alphabet with selfloop events
983  * @param rStates
984  * states to apply selfloop
985  *
986  * @exception Exception
987  * - rStates is not a subset of rGen.States() (id 100).
988  *
989  * <h4>Example:</h4>
990  * <table>
991  * <tr> <td> Generator G </td> <td> SelfLoop(G,Sigma={e,f},G.InitStates()) </td> </tr>
992  * <tr>
993  * <td> @image html tmp_selfloop_g.png </td>
994  * <td> @image html tmp_selfloopInit_gRes.png </td>
995  * </tr>
996  * </table>
997  *
998  * @ingroup GeneratorFunctions
999  */
1000 extern FAUDES_API void SelfLoop(Generator& rGen,const EventSet& rAlphabet,const StateSet& rStates);
1001 
1002 
1003 /** lagacy wrappet (pre 2.33) */
1004 extern FAUDES_API bool IsPrefixClosed(const Generator& rGen);
1005 
1006 
1007 } // namespace faudes
1008 
1009 #define FAUDES_REGULAR_H
1010 #endif
1011 
#define FAUDES_API
Definition: cfl_platform.h:85
IndexSet StateSet
Definition: cfl_indexset.h:296
NameSet EventSet
Definition: cfl_nameset.h:546
vGenerator Generator
TBaseVector< Generator > GeneratorVector
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 KleeneClosure(Generator &rGen)
void PrefixClosure(Generator &rGen)
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 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)

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