Projet Informatique Théorique 2016
Instructions et Documentation
automate.c
1 /*
2  * Ce fichier fait partie d'un projet de programmation donné en Licence 3
3  * à l'Université de Bordeaux
4  *
5  * Copyright (C) 2014, 2015 Adrien Boussicault
6  *
7  * This Library is free software: you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation, either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * This Library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this Library. If not, see <http://www.gnu.org/licenses/>.
19  */
20 
21 #include "automate.h"
22 #include "table.h"
23 #include "ensemble.h"
24 #include "outils.h"
25 #include "fifo.h"
26 
27 #include <search.h>
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <limits.h>
32 
33 #include <assert.h>
34 
35 #include <math.h>
36 
37 
38 int get_max_etat( const Automate* automate ){
39  A_FAIRE_RETURN( 0 );
40 }
41 
42 void action_get_min_etat( const intptr_t element, void* data ){
43  int * min = (int*) data;
44  if( *min > element ) *min = element;
45 }
46 
47 int get_min_etat( const Automate* automate ){
48  int min = INT_MAX;
49 
50  pour_tout_element( automate->etats, action_get_min_etat, &min );
51 
52  return min;
53 }
54 
55 
56 int comparer_cle(const Cle *a, const Cle *b) {
57  if( a->origine < b->origine )
58  return -1;
59  if( a->origine > b->origine )
60  return 1;
61  if( a->lettre < b->lettre )
62  return -1;
63  if( a->lettre > b->lettre )
64  return 1;
65  return 0;
66 }
67 
68 void print_cle( const Cle * a){
69  printf( "(%d, %c)" , a->origine, (char) (a->lettre) );
70 }
71 
72 void supprimer_cle( Cle* cle ){
73  xfree( cle );
74 }
75 
76 void initialiser_cle( Cle* cle, int origine, char lettre ){
77  cle->origine = origine;
78  cle->lettre = (int) lettre;
79 }
80 
81 Cle * creer_cle( int origine, char lettre ){
82  Cle * result = xmalloc( sizeof(Cle) );
83  initialiser_cle( result, origine, lettre );
84  return result;
85 }
86 
87 Cle * copier_cle( const Cle* cle ){
88  return creer_cle( cle->origine, cle->lettre );
89 }
90 
92  Automate * automate = xmalloc( sizeof(Automate) );
93  automate->etats = creer_ensemble( NULL, NULL, NULL );
94  automate->alphabet = creer_ensemble( NULL, NULL, NULL );
95  automate->transitions = creer_table(
96  ( int(*)(const intptr_t, const intptr_t) ) comparer_cle ,
97  ( intptr_t (*)( const intptr_t ) ) copier_cle,
98  ( void(*)(intptr_t) ) supprimer_cle
99  );
100  automate->initiaux = creer_ensemble( NULL, NULL, NULL );
101  automate->finaux = creer_ensemble( NULL, NULL, NULL );
102  automate->vide = creer_ensemble( NULL, NULL, NULL );
103  return automate;
104 }
105 
106 Automate * translater_automate_entier( const Automate* automate, int translation ){
107  Automate * res = creer_automate();
108 
110  for(
111  it = premier_iterateur_ensemble( get_etats( automate ) );
112  ! iterateur_ensemble_est_vide( it );
113  it = iterateur_suivant_ensemble( it )
114  ){
115  ajouter_etat( res, get_element( it ) + translation );
116  }
117 
118  for(
119  it = premier_iterateur_ensemble( get_initiaux( automate ) );
120  ! iterateur_ensemble_est_vide( it );
121  it = iterateur_suivant_ensemble( it )
122  ){
123  ajouter_etat_initial( res, get_element( it ) + translation );
124  }
125 
126  for(
127  it = premier_iterateur_ensemble( get_finaux( automate ) );
128  ! iterateur_ensemble_est_vide( it );
129  it = iterateur_suivant_ensemble( it )
130  ){
131  ajouter_etat_final( res, get_element( it ) + translation );
132  }
133 
134  // On ajoute les lettres
135  for(
136  it = premier_iterateur_ensemble( get_alphabet( automate ) );
137  ! iterateur_ensemble_est_vide( it );
138  it = iterateur_suivant_ensemble( it )
139  ){
140  ajouter_lettre( res, (char) get_element( it ) );
141  }
142 
143  Table_iterateur it1;
144  Ensemble_iterateur it2;
145  for(
146  it1 = premier_iterateur_table( automate->transitions );
147  ! iterateur_est_vide( it1 );
148  it1 = iterateur_suivant_table( it1 )
149  ){
150  Cle * cle = (Cle*) get_cle( it1 );
151  Ensemble * fins = (Ensemble*) get_valeur( it1 );
152  for(
153  it2 = premier_iterateur_ensemble( fins );
154  ! iterateur_ensemble_est_vide( it2 );
155  it2 = iterateur_suivant_ensemble( it2 )
156  ){
157  int fin = get_element( it2 );
159  res, cle->origine + translation, cle->lettre, fin + translation
160  );
161  }
162  };
163 
164  return res;
165 }
166 
167 
168 void liberer_automate( Automate * automate ){
169  assert( automate );
170  liberer_ensemble( automate->vide );
171  liberer_ensemble( automate->finaux );
172  liberer_ensemble( automate->initiaux );
174  automate->transitions, ( void(*)(intptr_t) ) liberer_ensemble
175  );
176  liberer_table( automate->transitions );
177  liberer_ensemble( automate->alphabet );
178  liberer_ensemble( automate->etats );
179  xfree(automate);
180 }
181 
182 const Ensemble * get_etats( const Automate* automate ){
183  return automate->etats;
184 }
185 
186 const Ensemble * get_initiaux( const Automate* automate ){
187  return automate->initiaux;
188 }
189 
190 const Ensemble * get_finaux( const Automate* automate ){
191  return automate->finaux;
192 }
193 
194 const Ensemble * get_alphabet( const Automate* automate ){
195  return automate->alphabet;
196 }
197 
198 void ajouter_etat( Automate * automate, int etat ){
199  ajouter_element( automate->etats, etat );
200 }
201 
202 void ajouter_lettre( Automate * automate, char lettre ){
203  ajouter_element( automate->alphabet, lettre );
204 }
205 
207  Automate * automate, int origine, char lettre, int fin
208 ){
209  ajouter_etat( automate, origine );
210  ajouter_etat( automate, fin );
211  ajouter_lettre( automate, lettre );
212 
213  Cle cle;
214  initialiser_cle( &cle, origine, lettre );
215  Table_iterateur it = trouver_table( automate->transitions, (intptr_t) &cle );
216  Ensemble * ens;
217  if( iterateur_est_vide( it ) ){
218  ens = creer_ensemble( NULL, NULL, NULL );
219  add_table( automate->transitions, (intptr_t) &cle, (intptr_t) ens );
220  }else{
221  ens = (Ensemble*) get_valeur( it );
222  }
223  ajouter_element( ens, fin );
224 }
225 
227  Automate * automate, int etat_final
228 ){
229  ajouter_etat( automate, etat_final );
230  ajouter_element( automate->finaux, etat_final );
231 }
232 
234  Automate * automate, int etat_initial
235 ){
236  ajouter_etat( automate, etat_initial );
237  ajouter_element( automate->initiaux, etat_initial );
238 }
239 
240 const Ensemble * voisins( const Automate* automate, int origine, char lettre ){
241  Cle cle;
242  initialiser_cle( &cle, origine, lettre );
243  Table_iterateur it = trouver_table( automate->transitions, (intptr_t) &cle );
244  if( ! iterateur_est_vide( it ) ){
245  return (Ensemble*) get_valeur( it );
246  }else{
247  return automate->vide;
248  }
249 }
250 
252  const Automate* automate, int origine, char lettre
253 ){
254  Ensemble * res = creer_ensemble( NULL, NULL, NULL );
255  ajouter_elements( res, voisins( automate, origine, lettre ) );
256  return res;
257 }
258 
260  const Automate* automate, const Ensemble * etats_courants, char lettre
261 ){
262  Ensemble * res = creer_ensemble( NULL, NULL, NULL );
263 
265  for(
266  it = premier_iterateur_ensemble( etats_courants );
267  ! iterateur_ensemble_est_vide( it );
268  it = iterateur_suivant_ensemble( it )
269  ){
270  const Ensemble * fins = voisins(
271  automate, get_element( it ), lettre
272  );
273  ajouter_elements( res, fins );
274  }
275 
276  return res;
277 }
278 
280  const Automate* automate, const Ensemble * etats_courants, const char* mot
281 ){
282  int len = strlen( mot );
283  int i;
284  Ensemble * old = copier_ensemble( etats_courants );
285  Ensemble * new = old;
286  for( i=0; i<len; i++ ){
287  new = delta( automate, old, *(mot+i) );
288  liberer_ensemble( old );
289  old = new;
290  }
291  return new;
292 }
293 
295  const Automate* automate,
296  void (* action )( int origine, char lettre, int fin, void* data ),
297  void* data
298 ){
299  Table_iterateur it1;
300  Ensemble_iterateur it2;
301  for(
302  it1 = premier_iterateur_table( automate->transitions );
303  ! iterateur_est_vide( it1 );
304  it1 = iterateur_suivant_table( it1 )
305  ){
306  Cle * cle = (Cle*) get_cle( it1 );
307  Ensemble * fins = (Ensemble*) get_valeur( it1 );
308  for(
309  it2 = premier_iterateur_ensemble( fins );
310  ! iterateur_ensemble_est_vide( it2 );
311  it2 = iterateur_suivant_ensemble( it2 )
312  ){
313  int fin = get_element( it2 );
314  action( cle->origine, cle->lettre, fin, data );
315  }
316  };
317 }
318 
319 Automate* copier_automate( const Automate* automate ){
320  Automate * res = creer_automate();
321  Ensemble_iterateur it1;
322  // On ajoute les états de l'automate
323  for(
324  it1 = premier_iterateur_ensemble( get_etats( automate ) );
325  ! iterateur_ensemble_est_vide( it1 );
326  it1 = iterateur_suivant_ensemble( it1 )
327  ){
328  ajouter_etat( res, get_element( it1 ) );
329  }
330  // On ajoute les états initiaux
331  for(
332  it1 = premier_iterateur_ensemble( get_initiaux( automate ) );
333  ! iterateur_ensemble_est_vide( it1 );
334  it1 = iterateur_suivant_ensemble( it1 )
335  ){
336  ajouter_etat_initial( res, get_element( it1 ) );
337  }
338  // On ajoute les états finaux
339  for(
340  it1 = premier_iterateur_ensemble( get_finaux( automate ) );
341  ! iterateur_ensemble_est_vide( it1 );
342  it1 = iterateur_suivant_ensemble( it1 )
343  ){
344  ajouter_etat_final( res, get_element( it1 ) );
345  }
346  // On ajoute les lettres
347  for(
348  it1 = premier_iterateur_ensemble( get_alphabet( automate ) );
349  ! iterateur_ensemble_est_vide( it1 );
350  it1 = iterateur_suivant_ensemble( it1 )
351  ){
352  ajouter_lettre( res, (char) get_element( it1 ) );
353  }
354  // On ajoute les transitions
355  Table_iterateur it2;
356  for(
357  it2 = premier_iterateur_table( automate->transitions );
358  ! iterateur_est_vide( it2 );
359  it2 = iterateur_suivant_table( it2 )
360  ){
361  Cle * cle = (Cle*) get_cle( it2 );
362  Ensemble * fins = (Ensemble*) get_valeur( it2 );
363  for(
364  it1 = premier_iterateur_ensemble( fins );
365  ! iterateur_ensemble_est_vide( it1 );
366  it1 = iterateur_suivant_ensemble( it1 )
367  ){
368  int fin = get_element( it1 );
369  ajouter_transition( res, cle->origine, cle->lettre, fin );
370  }
371  }
372  return res;
373 }
374 
376  const Automate * automate, const Automate * automate_a_eviter
377 ){
378  if(
379  taille_ensemble( get_etats(automate) ) == 0 ||
380  taille_ensemble( get_etats(automate_a_eviter) ) == 0
381  ){
382  return copier_automate( automate );
383  }
384 
385  int translation =
386  get_max_etat( automate_a_eviter ) - get_min_etat( automate ) + 1;
387 
388  return translater_automate_entier( automate, translation );
389 
390 }
391 
393  const Automate* automate,
394  int origine, char lettre, int fin
395 ){
396  return est_dans_l_ensemble( voisins( automate, origine, lettre ), fin );
397 }
398 
399 int est_un_etat_de_l_automate( const Automate* automate, int etat ){
400  return est_dans_l_ensemble( get_etats( automate ), etat );
401 }
402 
403 int est_un_etat_initial_de_l_automate( const Automate* automate, int etat ){
404  return est_dans_l_ensemble( get_initiaux( automate ), etat );
405 }
406 
407 int est_un_etat_final_de_l_automate( const Automate* automate, int etat ){
408  return est_dans_l_ensemble( get_finaux( automate ), etat );
409 }
410 
411 int est_une_lettre_de_l_automate( const Automate* automate, char lettre ){
412  return est_dans_l_ensemble( get_alphabet( automate ), lettre );
413 }
414 
415 void print_ensemble_2( const intptr_t ens ){
416  print_ensemble( (Ensemble*) ens, NULL );
417 }
418 
419 void print_lettre( intptr_t c ){
420  printf("%c", (char) c );
421 }
422 
423 void print_automate( const Automate * automate ){
424  printf("- Etats : ");
425  print_ensemble( get_etats( automate ), NULL );
426  printf("\n- Initiaux : ");
427  print_ensemble( get_initiaux( automate ), NULL );
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 : ");
433  print_table(
434  automate->transitions,
435  ( void (*)( const intptr_t ) ) print_cle,
436  ( void (*)( const intptr_t ) ) print_ensemble_2,
437  ""
438  );
439  printf("\n");
440 }
441 
442 int le_mot_est_reconnu( const Automate* automate, const char* mot ){
443  Ensemble * arrivee = delta_star( automate, get_initiaux(automate) , mot );
444 
445  int result = 0;
446 
448  for(
449  it = premier_iterateur_ensemble( arrivee );
450  ! iterateur_ensemble_est_vide( it );
451  it = iterateur_suivant_ensemble( it )
452  ){
453  if( est_un_etat_final_de_l_automate( automate, get_element(it) ) ){
454  result = 1;
455  break;
456  }
457  }
458  liberer_ensemble( arrivee );
459  return result;
460 }
461 
462 Automate * mot_to_automate( const char * mot ){
463  Automate * automate = creer_automate();
464  int i = 0;
465  int size = strlen( mot );
466  for( i=0; i < size; i++ ){
467  ajouter_transition( automate, i, mot[i], i+1 );
468  }
469  ajouter_etat_initial( automate, 0 );
470  ajouter_etat_final( automate, size );
471  return automate;
472 }
473 
475  const Automate * automate_1, const Automate * automate_2
476 ){
477  A_FAIRE_RETURN( NULL );
478 }
479 
480 Ensemble* etats_accessibles( const Automate * automate, int etat ){
481  A_FAIRE_RETURN( NULL );
482 }
483 
484 Ensemble* accessibles( const Automate * automate ){
485  A_FAIRE_RETURN( NULL );
486 }
487 
488 Automate *automate_accessible( const Automate * automate ){
489  A_FAIRE_RETURN( NULL );
490 }
491 
492 Automate *miroir( const Automate * automate){
493  A_FAIRE_RETURN( NULL );
494 }
495 
497  const Automate* automate_1, const Automate* automate_2
498 ){
499  A_FAIRE_RETURN( NULL );
500 }
501 
Ensemble * etats_accessibles(const Automate *automate, int etat)
Definition: automate.c:480
Le type d'un automate.
Definition: automate.h:39
void liberer_automate(Automate *automate)
Détruit un automate.
Definition: automate.c:168
Automate * miroir(const Automate *automate)
Definition: automate.c:492
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.
Definition: automate.c:392
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...
Definition: automate.c:279
Automate * creer_automate_du_melange(const Automate *automate1, const Automate *automate2)
Definition: automate.c:496
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...
Definition: automate.c:259
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.
Definition: automate.c:403
Automate * mot_to_automate(const char *mot)
Renvoie un automate qui reconnaît un unique mot passé en paramètre.
Definition: automate.c:462
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.
Definition: automate.c:411
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.
Definition: automate.c:399
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...
Definition: automate.c:251
Table_iterateur premier_iterateur_table(const Table *table)
Renvoie un itérateur positionné sur la première association de la table.
Definition: table.c:251
intptr_t get_cle(Table_iterateur it)
Renvoie la clé de l'association pointée par l'itérateur passé en paramètre.
Definition: table.c:47
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.
Definition: automate.c:442
void ajouter_etat(Automate *automate, int etat)
Ajoute un état à un automate passé en paramètre.
Definition: automate.c:198
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...
Definition: automate.c:106
void ajouter_transition(Automate *automate, int origine, char lettre, int fin)
Ajoute une transition à l'automate passé en paramètre.
Definition: automate.c:206
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...
Definition: table.c:131
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.
Definition: automate.c:407
Automate * creer_automate()
Crée un automate vide, sans états, sans lettres et sans transitions.
Definition: automate.c:91
int get_max_etat(const Automate *automate)
Definition: automate.c:38
Ensemble * accessibles(const Automate *automate)
Definition: automate.c:484
const Ensemble * get_finaux(const Automate *automate)
Renvoie l'ensemble des états finaux d'un automate.
Definition: automate.c:190
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...
Definition: automate.c:294
const Ensemble * get_initiaux(const Automate *automate)
Renvoie l'ensemble des états intiaux d'un automate.
Definition: automate.c:186
Table_iterateur iterateur_suivant_table(Table_iterateur iterator)
Renvoie l'itérateur suivant.
Definition: table.c:269
intptr_t get_valeur(Table_iterateur it)
Renvoie la valeur de l'association pointée par l'itérateur passé en paramètre.
Definition: table.c:52
void print_automate(const Automate *automate)
Affiche sur l'entrée standard (stdout) l'automate passé en paramètre.
Definition: automate.c:423
void ajouter_lettre(Automate *automate, char lettre)
Ajoute une lettre à l'alphabet d'un automate passé en paramètre.
Definition: automate.c:202
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...
Definition: table.c:192
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é...
Definition: table.c:227
const Ensemble * get_etats(const Automate *automate)
Renvoie l'ensemble des états d'un automate.
Definition: automate.c:182
int iterateur_est_vide(Table_iterateur iterator)
Renvoie 1 si l'itérateur passé en paramètre est vide. Renvoie 0 sinon.
Definition: table.c:265
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...
Definition: table.c:241
Automate * automate_accessible(const Automate *automate)
Definition: automate.c:488
Automate * creer_union_des_automates(const Automate *automate_1, const Automate *automate_2)
Definition: automate.c:474
void ajouter_etat_final(Automate *automate, int etat_final)
Ajoute un état final à un automate passé en paramètre.
Definition: automate.c:226
void ajouter_etat_initial(Automate *automate, int etat_initial)
Ajoute un état initial à un automate passé en paramètre.
Definition: automate.c:233
const Ensemble * get_alphabet(const Automate *automate)
Renvoie l'alphabet d'un automate.
Definition: automate.c:194
int get_min_etat(const Automate *automate)
Renvoie l'état ayant le numéro le plus petit de l'automate passé en paramètre.
Definition: automate.c:47
Automate * copier_automate(const Automate *automate)
Copie un automate.
Definition: automate.c:319
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.
Definition: table.c:117
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.
Definition: table.c:137
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...
Definition: automate.c:375
Definition: automate.h:50