42 void action_get_min_etat(
const intptr_t element,
void* data ){
43 int * min = (
int*) data;
44 if( *min > element ) *min = element;
50 pour_tout_element( automate->etats, action_get_min_etat, &min );
56 int comparer_cle(
const Cle *a,
const Cle *b) {
57 if( a->origine < b->origine )
59 if( a->origine > b->origine )
61 if( a->lettre < b->lettre )
63 if( a->lettre > b->lettre )
68 void print_cle(
const Cle * a){
69 printf(
"(%d, %c)" , a->origine, (
char) (a->lettre) );
72 void supprimer_cle(
Cle* cle ){
76 void initialiser_cle(
Cle* cle,
int origine,
char lettre ){
77 cle->origine = origine;
78 cle->lettre = (int) lettre;
81 Cle * creer_cle(
int origine,
char lettre ){
82 Cle * result = xmalloc(
sizeof(
Cle) );
83 initialiser_cle( result, origine, lettre );
87 Cle * copier_cle(
const Cle* cle ){
88 return creer_cle( cle->origine, cle->lettre );
93 automate->etats = creer_ensemble( NULL, NULL, NULL );
94 automate->alphabet = creer_ensemble( NULL, NULL, NULL );
96 (
int(*)(
const intptr_t,
const intptr_t) ) comparer_cle ,
97 ( intptr_t (*)(
const intptr_t ) ) copier_cle,
98 (
void(*)(intptr_t) ) supprimer_cle
100 automate->initiaux = creer_ensemble( NULL, NULL, NULL );
101 automate->finaux = creer_ensemble( NULL, NULL, NULL );
102 automate->vide = creer_ensemble( NULL, NULL, NULL );
111 it = premier_iterateur_ensemble(
get_etats( automate ) );
112 ! iterateur_ensemble_est_vide( it );
113 it = iterateur_suivant_ensemble( it )
119 it = premier_iterateur_ensemble(
get_initiaux( automate ) );
120 ! iterateur_ensemble_est_vide( it );
121 it = iterateur_suivant_ensemble( it )
127 it = premier_iterateur_ensemble(
get_finaux( automate ) );
128 ! iterateur_ensemble_est_vide( it );
129 it = iterateur_suivant_ensemble( it )
136 it = premier_iterateur_ensemble(
get_alphabet( automate ) );
137 ! iterateur_ensemble_est_vide( it );
138 it = iterateur_suivant_ensemble( it )
153 it2 = premier_iterateur_ensemble( fins );
154 ! iterateur_ensemble_est_vide( it2 );
155 it2 = iterateur_suivant_ensemble( it2 )
157 int fin = get_element( it2 );
159 res, cle->origine + translation, cle->lettre, fin + translation
170 liberer_ensemble( automate->vide );
171 liberer_ensemble( automate->finaux );
172 liberer_ensemble( automate->initiaux );
174 automate->transitions, (
void(*)(intptr_t) ) liberer_ensemble
177 liberer_ensemble( automate->alphabet );
178 liberer_ensemble( automate->etats );
183 return automate->etats;
187 return automate->initiaux;
191 return automate->finaux;
195 return automate->alphabet;
199 ajouter_element( automate->etats, etat );
203 ajouter_element( automate->alphabet, lettre );
207 Automate * automate,
int origine,
char lettre,
int fin
214 initialiser_cle( &cle, origine, lettre );
218 ens = creer_ensemble( NULL, NULL, NULL );
219 add_table( automate->transitions, (intptr_t) &cle, (intptr_t) ens );
223 ajouter_element( ens, fin );
230 ajouter_element( automate->finaux, etat_final );
234 Automate * automate,
int etat_initial
237 ajouter_element( automate->initiaux, etat_initial );
240 const Ensemble * voisins(
const Automate* automate,
int origine,
char lettre ){
242 initialiser_cle( &cle, origine, lettre );
247 return automate->vide;
252 const Automate* automate,
int origine,
char lettre
254 Ensemble * res = creer_ensemble( NULL, NULL, NULL );
255 ajouter_elements( res, voisins( automate, origine, lettre ) );
262 Ensemble * res = creer_ensemble( NULL, NULL, NULL );
266 it = premier_iterateur_ensemble( etats_courants );
267 ! iterateur_ensemble_est_vide( it );
268 it = iterateur_suivant_ensemble( it )
271 automate, get_element( it ), lettre
273 ajouter_elements( res, fins );
282 int len = strlen( mot );
284 Ensemble * old = copier_ensemble( etats_courants );
286 for( i=0; i<len; i++ ){
287 new =
delta( automate, old, *(mot+i) );
288 liberer_ensemble( old );
296 void (* action )(
int origine,
char lettre,
int fin,
void* data ),
309 it2 = premier_iterateur_ensemble( fins );
310 ! iterateur_ensemble_est_vide( it2 );
311 it2 = iterateur_suivant_ensemble( it2 )
313 int fin = get_element( it2 );
314 action( cle->origine, cle->lettre, fin, data );
324 it1 = premier_iterateur_ensemble(
get_etats( automate ) );
325 ! iterateur_ensemble_est_vide( it1 );
326 it1 = iterateur_suivant_ensemble( it1 )
332 it1 = premier_iterateur_ensemble(
get_initiaux( automate ) );
333 ! iterateur_ensemble_est_vide( it1 );
334 it1 = iterateur_suivant_ensemble( it1 )
340 it1 = premier_iterateur_ensemble(
get_finaux( automate ) );
341 ! iterateur_ensemble_est_vide( it1 );
342 it1 = iterateur_suivant_ensemble( it1 )
348 it1 = premier_iterateur_ensemble(
get_alphabet( automate ) );
349 ! iterateur_ensemble_est_vide( it1 );
350 it1 = iterateur_suivant_ensemble( it1 )
364 it1 = premier_iterateur_ensemble( fins );
365 ! iterateur_ensemble_est_vide( it1 );
366 it1 = iterateur_suivant_ensemble( it1 )
368 int fin = get_element( it1 );
379 taille_ensemble(
get_etats(automate) ) == 0 ||
380 taille_ensemble(
get_etats(automate_a_eviter) ) == 0
394 int origine,
char lettre,
int fin
396 return est_dans_l_ensemble( voisins( automate, origine, lettre ), fin );
400 return est_dans_l_ensemble(
get_etats( automate ), etat );
404 return est_dans_l_ensemble(
get_initiaux( automate ), etat );
408 return est_dans_l_ensemble(
get_finaux( automate ), etat );
412 return est_dans_l_ensemble(
get_alphabet( automate ), lettre );
415 void print_ensemble_2(
const intptr_t ens ){
416 print_ensemble( (
Ensemble*) ens, NULL );
419 void print_lettre( intptr_t c ){
420 printf(
"%c", (
char) c );
424 printf(
"- Etats : ");
425 print_ensemble(
get_etats( automate ), NULL );
426 printf(
"\n- Initiaux : ");
428 printf(
"\n- Finaux : ");
429 print_ensemble(
get_finaux( automate ), NULL );
430 printf(
"\n- Alphabet : ");
431 print_ensemble(
get_alphabet( automate ), print_lettre );
432 printf(
"\n- Transitions : ");
434 automate->transitions,
435 ( void (*)(
const intptr_t ) ) print_cle,
436 (
void (*)(
const intptr_t ) ) print_ensemble_2,
449 it = premier_iterateur_ensemble( arrivee );
450 ! iterateur_ensemble_est_vide( it );
451 it = iterateur_suivant_ensemble( it )
458 liberer_ensemble( arrivee );
465 int size = strlen( mot );
466 for( i=0; i < size; i++ ){
477 A_FAIRE_RETURN( NULL );
481 A_FAIRE_RETURN( NULL );
485 A_FAIRE_RETURN( NULL );
489 A_FAIRE_RETURN( NULL );
493 A_FAIRE_RETURN( NULL );
499 A_FAIRE_RETURN( NULL );
Ensemble * etats_accessibles(const Automate *automate, int etat)
void liberer_automate(Automate *automate)
Détruit un automate.
Automate * miroir(const Automate *automate)
int est_une_transition_de_l_automate(const Automate *automate, int origine, char lettre, int fin)
Renvoie 1 si ('origine', 'lettre', 'fin') est une transition de l'automate et 0 sinon.
Ensemble * delta_star(const Automate *automate, const Ensemble *etats_courants, const char *mot)
Renvoie l'ensemble des états accessibles à partir d'un ensemble d'états donné en paramètre et en lisa...
Automate * creer_automate_du_melange(const Automate *automate1, const Automate *automate2)
Ensemble * delta(const Automate *automate, const Ensemble *etats_courants, char lettre)
Renvoie l'ensemble des états accéssibles à partir d'un ensemble d'états donné en paramètre et en lisa...
int est_un_etat_initial_de_l_automate(const Automate *automate, int etat)
Renvoie 1 si ('etat') est un état initial de l'automate et 0 sinon.
Automate * mot_to_automate(const char *mot)
Renvoie un automate qui reconnaît un unique mot passé en paramètre.
int est_une_lettre_de_l_automate(const Automate *automate, char lettre)
Renvoie 1 si ('etat') est une lettre de l'automate et 0 sinon.
int est_un_etat_de_l_automate(const Automate *automate, int etat)
Renvoie 1 si ('etat') est un état de l'automate et 0 sinon.
Ensemble * delta1(const Automate *automate, int origine, char lettre)
Renvoie l'ensemble des états accessibles à partir d'un état donné en paramètre et en lisant une lettr...
Table_iterateur premier_iterateur_table(const Table *table)
Renvoie un itérateur positionné sur la première association de la table.
intptr_t get_cle(Table_iterateur it)
Renvoie la clé de l'association pointée par l'itérateur passé en paramètre.
int le_mot_est_reconnu(const Automate *automate, const char *mot)
Renvoie vrai si le mot passé en paramètre est reconu par l'automate passé en paramètre, et renvoie 0 sinon.
void ajouter_etat(Automate *automate, int etat)
Ajoute un état à un automate passé en paramètre.
Automate * translater_automate_entier(const Automate *automate, int translation)
Crée une copie de l'automate passé en paramètre dont les numéros de tous les états ont été translatés...
void ajouter_transition(Automate *automate, int origine, char lettre, int fin)
Ajoute une transition à l'automate passé en paramètre.
void liberer_table(Table *table)
Cette fonction détruit une table. La mémoire qui a été allouée par la table pour stocker les clés son...
int est_un_etat_final_de_l_automate(const Automate *automate, int etat)
Renvoie 1 si ('etat') est un état final initial de l'automate et 0 sinon.
Automate * creer_automate()
Crée un automate vide, sans états, sans lettres et sans transitions.
int get_max_etat(const Automate *automate)
Ensemble * accessibles(const Automate *automate)
const Ensemble * get_finaux(const Automate *automate)
Renvoie l'ensemble des états finaux d'un automate.
void pour_toute_transition(const Automate *automate, void(*action)(int origine, char lettre, int fin, void *data), void *data)
La fonction passe en revue toutes les transitions de l'automate et appelle la fonction passée en para...
const Ensemble * get_initiaux(const Automate *automate)
Renvoie l'ensemble des états intiaux d'un automate.
Table_iterateur iterateur_suivant_table(Table_iterateur iterator)
Renvoie l'itérateur suivant.
intptr_t get_valeur(Table_iterateur it)
Renvoie la valeur de l'association pointée par l'itérateur passé en paramètre.
void print_automate(const Automate *automate)
Affiche sur l'entrée standard (stdout) l'automate passé en paramètre.
void ajouter_lettre(Automate *automate, char lettre)
Ajoute une lettre à l'alphabet d'un automate passé en paramètre.
void pour_toute_valeur_table(const Table *table, void(*action)(intptr_t valeur))
La fonction passe en revue toutes les valeurs de la table passée en paramètre et apelle la fonction p...
void print_table(Table *table, void(*print_cle)(const intptr_t cle), void(*print_valeur)(const intptr_t valeur), const char *text_de_fin)
Affiche la table. Vous devez donner en paramètres de print_table, des fonctions pour afficher les clé...
const Ensemble * get_etats(const Automate *automate)
Renvoie l'ensemble des états d'un automate.
int iterateur_est_vide(Table_iterateur iterator)
Renvoie 1 si l'itérateur passé en paramètre est vide. Renvoie 0 sinon.
Table_iterateur trouver_table(const Table *table, const intptr_t cle)
Renvoie un itérateur positionné sur l'association dont la clé est identique (pour la fonction de comp...
Automate * automate_accessible(const Automate *automate)
Automate * creer_union_des_automates(const Automate *automate_1, const Automate *automate_2)
void ajouter_etat_final(Automate *automate, int etat_final)
Ajoute un état final à un automate passé en paramètre.
void ajouter_etat_initial(Automate *automate, int etat_initial)
Ajoute un état initial à un automate passé en paramètre.
const Ensemble * get_alphabet(const Automate *automate)
Renvoie l'alphabet d'un automate.
int get_min_etat(const Automate *automate)
Renvoie l'état ayant le numéro le plus petit de l'automate passé en paramètre.
Automate * copier_automate(const Automate *automate)
Copie un automate.
Table * creer_table(int(*comparer_cle)(const intptr_t cle1, const intptr_t cle2), intptr_t(*copier_cle)(const intptr_t cle), void(*supprimer_cle)(intptr_t cle))
Renvoie une nouvelle table.
void add_table(Table *table, const intptr_t cle, const intptr_t valeur)
La fonction add_table() ajoute une association entre une clé et une valeur. Pour cela, add_table(), crée une copie de la clé passée en paramètre, l'enregistre dans la table et l'associe à la valeur passée en paramètre. La mémoire de la copie de la clé est gérée par la table. La mémoire de la clé passée en paramètre reste à la charge de l'utilisateur.
Automate * translater_automate(const Automate *automate, const Automate *automate_a_eviter)
Crée une copie de l'automate passé en paramètre. Les entiers des états du nouvel automate évitent ceu...