This repository has been archived by the owner on Jan 30, 2023. It is now read-only.
-
-
Notifications
You must be signed in to change notification settings - Fork 7
/
automataC.h
170 lines (136 loc) · 5.37 KB
/
automataC.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <stdint.h>
typedef uint64_t uint64;
typedef unsigned int uint;
typedef Automate Automaton;
typedef NAutomate NAutomaton;
struct Dict
{
int *e;
int n;
};
typedef struct Dict Dict;
Dict NewDict (int n);
void FreeDict (Dict d);
void printDict (Dict d);
void dictAdd (Dict *d, int e); //ajoute un élément au dictionnaire (même s'il était déjà présent)
Automaton NewAutomaton (int n, int na);
void ReallocNAutomaton (NAutomaton *a, int n);
void FreeAutomaton (Automaton *a);
void FreeNAutomaton (NAutomaton *a);
Automaton CopyAutomaton (Automaton a, int nalloc, int naalloc);
Automaton PieceAutomaton (Automaton a, int *w, int n, int e); //donne un automate reconnaissant w(w^(-1)L) où L est le langage de a partant de e
void init (Automaton *a);
void printAutomaton (Automaton a);
void plotTikZ (Automaton a, const char **labels, const char *graph_name, double sx, double sy);
bool equalsAutomaton (Automaton a1, Automaton a2); //détermine si les automates sont les mêmes (différents si états permutés)
inline int contract (int i1, int i2, int n1);
inline int geti1 (int c, int n1);
inline int geti2 (int c, int n1);
Automaton Product (Automaton a1, Automaton a2, Dict d, bool verb);
void AddEtat (Automaton *a, bool final);
struct Etats
{
int *e;
int n;
};
typedef struct Etats Etats;
Etats NewEtats (int n);
void FreeEtats (Etats e);
void initEtats (Etats e);
void printEtats (Etats e);
bool equals (Etats e1, Etats e2);
Etats copyEtats (Etats e);
struct ListEtats
{
Etats *e;
int n;
};
typedef struct ListEtats ListEtats;
void printListEtats (ListEtats l);
bool AddEl (ListEtats *l, Etats e, int* res); //ajoute un élément s'il n'est pas déjà dans la liste
void AddEl2 (ListEtats *l, Etats e); //ajoute un élément même s'il est déjà dans la liste
////////////////
struct Etats2
{
uint n;
uint64 *e;
};
typedef struct Etats2 Etats2;
Etats2 NewEtats2 (int n);
void FreeEtats2 (Etats2 e);
void initEtats2 (Etats2 e);
void printEtats2 (Etats2 e);
bool isNullEtats2 (Etats2 e);
bool equalsEtats2 (Etats2 e1, Etats2 e2);
inline bool hasEtats2 (Etats2 e, uint64 i);
Etats2 copyEtats2 (Etats2 e);
void addEtat (Etats2 *e, uint64 i);
struct ListEtats2
{
Etats2 *e;
int n; //nombre d'états
int na; //mémoire allouée
};
typedef struct ListEtats2 ListEtats2;
ListEtats2 NewListEtats2(int n, int na);
void ReallocListEtats2(ListEtats2* l, int n, bool marge);
void FreeListEtats2 (ListEtats2* l);
void printListEtats2 (ListEtats2 l);
//bool AddEtats2 (ListEtats2 *l, Etats2 e, int* res); //ajoute un élément s'il n'est pas déjà dans la liste
//void addEtats2 (ListEtats2 *l, Etats2 e); //ajoute un élément même s'il est déjà dans la liste
////////////////
//inverse d'un dictionnaire
struct InvertDict
{
Dict *d;
int n;
};
typedef struct InvertDict InvertDict;
InvertDict NewInvertDict (int n);
InvertDict invertDict (Dict d);
void FreeInvertDict (InvertDict id);
void printInvertDict (InvertDict id);
void putEtat (Etats *f, int ef); ////////////////////////////////// à améliorer !!!!
void Determinise_rec (Automaton a, InvertDict id, Automaton* r, ListEtats* l, bool onlyfinals, bool nof, int niter);
Automaton Determinise (Automaton a, Dict d, bool noempty, bool onlyfinals, bool nof, bool verb);
Automaton DeterminiseN (NAutomaton a, bool puits);
//change l'alphabet en dupliquant des arêtes si nécessaire
//the result is assumed deterministic !!!!
Automaton Duplicate (Automaton a, InvertDict id, int na2, bool verb);
//ajoute tous les mots qui se complètent en un mot du langage en ajoutant des 0 à la fin
void ZeroComplete (Automaton a, int l0, bool verb);
//retire tous les états à partir desquels il n'y a pas de chemin infini
Automaton emonde_inf (Automaton a, bool verb);
//Compute the transposition, assuming it is deterministic
Automaton TransposeDet (Automaton a);
//Compute the transposition
NAutomaton Transpose (Automaton a);
//Tarjan algorithm
int StronglyConnectedComponents (Automaton a, int *res);
//retire tous les états non accessible ou non co-accessible
Automaton emonde (Automaton a, bool verb);
//retire tous les états non accessible
Automaton emondeI (Automaton a, bool verb);
Automaton SubAutomaton (Automaton a, Dict d, bool verb);
//permute les labels des arêtes
//l donne les anciens indices à partir des nouveaux
Automaton Permut (Automaton a, int *l, int na, bool verb);
//idem mais SUR PLACE
void PermutOP (Automaton a, int *l, int na, bool verb);
//minimisation par l'algo d'Hopcroft
//voir "Around Hopcroft’s Algorithm" de Manuel BACLET and Claire PAGETTI
Automaton Minimise (Automaton a, bool verb);
void DeleteVertexOP (Automaton *a, int e);
Automaton DeleteVertex (Automaton a, int e);
//détermine si les langages des automates sont les mêmes
//le dictionnaires donne les lettres de a2 en fonction de celles de a1 (-1 si la lettre de a1 ne correspond à aucune lettre de a2). Ce dictionnaire est supposé inversible.
//if minimized is true, the automaton a1 and a2 are assumed to be minimal.
bool equalsLangages (Automaton *a1, Automaton *a2, Dict a1toa2, bool minimized);
//détermine si le langage de l'automate est vide
bool emptyLangage (Automaton a);
//determine if the automaton is complete (i.e. with his hole state)
bool IsCompleteAutomaton (Automaton a);
//complete the automaton (i.e. add a hole state if necessary)
bool CompleteAutomaton (Automaton *a);
//copy the automaton with a new bigger alphabet
Automaton BiggerAlphabet (Automaton a, Dict d, int nna);