#include #include #include #include #define TRUE 1 #define FALSE 0 #define TRACEON FALSE #define MAX_ETATS 50 #define MAX_ALPHA 128 #define MAX_TRANS 5 #define MAX_L_MOT (MAX_ETATS-2) #define DIM_LISTE (MAX_L_MOT*MAX_L_MOT) /* MAX_ETATS nombre maximum d'etats qu'un automate peut avoir /* MAX_ALPHA differentes etiquettes existantes pour les transitions (set ASCII) /* MAX_TRANS nombre maximum de transitions avec la meme etiquette depuis un meme etat /* MAX_L_MOT longueur maximale d'un mot a' traiter /* DIM_LISTE dimension de la liste des sousmots d'une longueur donne' /****************************************************************************** Projet d'Algorithmique: Outil de Recherche de Sousmots Licence Informatique 1999-2000, Universite de Marne la Vallee (FRANCE) Copyright (C) 2000 Daniele Raffo mars-avril 2000 This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *******************************************************************************/ /* modele utilise' pour l'automate */ typedef struct { int table[2*MAX_ETATS][MAX_ALPHA][MAX_TRANS]; /* table des transitions */ int status[2*MAX_ETATS]; /* status = 0 : etat */ /* 1 : etat initial */ /* 2 : etat terminal */ /* 3 : etat initial et terminal */ /* -1 : nonexistent */ } automate; /* modele utilise' pour garder la liste des sousmots d'une longueur donnee */ typedef struct { char sousmot[MAX_L_MOT]; /* sousmot */ int terminus; /* l'etat ou' on arrive quand on lit la derniere lettre du sousmot */ int unique; /* flag: si TRUE ce sousmot distingue le deux mots */ } liste_sousmots; int equivhalt; /* flag: si TRUE non-equivalence des deux automates */ int dummy; /* variables dummy */ automate adummy; main(int argc, char *argv[]) { void main_interactif(char *nomprog); void main_ligne_de_commande(int argc, char *argv[]); if (argc==1) main_interactif(argv[0]); else main_ligne_de_commande(argc, argv); } void main_interactif(char *nomprog) { void init_automate(automate *a); int lit_fichier(char *afile, automate *a); void ecrit_automate(FILE *fp, const automate *a); void error(int erreur, int datanum, char *datastr); int equiv_automate(char *afile1, char *afile2); automate automate_sousmots(const char mot[]); void tous_les_sousmots(FILE *fp, const char *mot_a_traiter); void distingue(FILE *fp, const char *mot1, const char *mot2); int output_sur_ecran(void); automate autom1, autom2; char fichier1[80]; char fichier2[80]; char mot1[MAX_L_MOT]; char mot2[MAX_L_MOT]; FILE *outputp; char outputfile[80]; char choix; int reponse; while (TRUE) { fprintf(stdout, "\n\n\n\n ----------------------------------------------------------------------"); fprintf(stdout, "\n Projet d'Algorithmique: Outil de Recherche de Sousmots"); fprintf(stdout, "\n\n Licence Informatique"); fprintf(stdout, "\n Universite de Marne la Vallee (FRANCE)"); fprintf(stdout, "\n\n Copyright (C) 2000 Daniele Raffo "); fprintf(stdout, "\n\n Ce programme est libre et vous etes encourage' a' le redistribuer"); fprintf(stdout, "\n sous les conditions du Licence Publique Generale GNU."); fprintf(stdout, "\n ----------------------------------------------------------------------"); fprintf(stdout, "\n\n\n %s -help pour les instructions sur l'usage en ligne de commande", nomprog); fprintf(stdout, "\n\n 1) Examiner un automate"); fprintf(stdout, "\n 2) Tester l'equivalence de deux AFD complets"); fprintf(stdout, "\n 3) Creer l'AFD complet des sousmots d'un mot"); fprintf(stdout, "\n 4) Lister les sousmots d'un mot"); fprintf(stdout, "\n 5) Calculer les sousmots qui distinguent deux mots"); fprintf(stdout, "\n\n X) Sortie"); fprintf(stdout, "\n\n\nOperation: "); fflush(stdin); scanf("%c", &choix); /* c'est mieux de nettoyer toujours le stdin avant d'y lire avec le scanf */ fprintf(stdout, "\n"); switch(toupper(choix)) { case '1': fprintf(stdout, "Nom du fichier: "); fflush(stdin); scanf("%[^\n]", fichier1); init_automate(&autom1); dummy=lit_fichier(fichier1, &autom1); ecrit_automate(stdout, &autom1); break; case '2': fprintf(stdout, "Nom du premier fichier: "); fflush(stdin); scanf("%[^\n]", fichier1); fprintf(stdout, "Nom du deuxieme fichier: "); fflush(stdin); scanf("%[^\n]", fichier2); reponse=equiv_automate(fichier1, fichier2); fprintf(stdout, "\n\nLes deux automates "); if (reponse) fprintf(stdout, "ne reconnaissent pas le meme langage"); else fprintf(stdout, "reconnaissent le meme langage"); break; case '3': fprintf(stdout, "Mot: "); fflush(stdin); scanf("%[^\n]", mot1); init_automate(&autom1); autom1=automate_sousmots(mot1); if (output_sur_ecran()) ecrit_automate(stdout, &autom1); else { fprintf(stdout, "Fichier de output: "); fflush(stdin); scanf("%[^\n]", &outputfile); if ((outputp=fopen(outputfile, "w"))==0) error(5, 0, outputfile); else ecrit_automate(outputp, &autom1); fclose(outputp); /* pas de probleme pour stdout, il ne sera pas ferme' */ } break; case '4': fprintf(stdout, "Mot: "); fflush(stdin); scanf("%[^\n]", mot1); init_automate(&autom1); autom1=automate_sousmots(mot1); if (output_sur_ecran()) tous_les_sousmots(stdout, mot1); else { fprintf(stdout, "Fichier de output: "); fflush(stdin); scanf("%[^\n]", &outputfile); if ((outputp=fopen(outputfile, "w"))==0) error(5, 0, outputfile); else tous_les_sousmots(outputp, mot1); fclose(outputp); } break; case '5': fprintf(stdout, "Premier mot: "); fflush(stdin); scanf("%[^\n]", mot1); fprintf(stdout, "Deuxieme mot: "); fflush(stdin); scanf("%[^\n]", mot2); if (output_sur_ecran()) distingue(stdout, mot1, mot2); else { fprintf(stdout, "Fichier de output: "); fflush(stdin); scanf("%[^\n]", &outputfile); if ((outputp=fopen(outputfile, "w"))==0) error(5, 0, outputfile); else distingue(outputp, mot1, mot2); fclose(outputp); } break; case 'X': exit(0); } } } void main_ligne_de_commande(int argc, char *argv[]) { void init_automate(automate *a); int lit_fichier(char *afile, automate *a); void ecrit_automate(FILE *fp, const automate *a); void error(int erreur, int datanum, char *datastr); int equiv_automate(char *afile1, char *afile2); void tous_les_sousmots(FILE *fp, const char *mot_a_traiter); void distingue(FILE *fp, const char *mot1, const char *mot2); automate autom; FILE *reference; if ((!strcmp(argv[1],"-e"))&&(argc==4)) exit(equiv_automate(argv[2], argv[3])); else if ((!strcmp(argv[1],"-m"))&&(argc==4)) distingue(stdout, argv[2], argv[3]); else if ((!strcmp(argv[1],"-m"))&&(argc==5)) { if ((reference=fopen(argv[4], "w"))==0) error(5, 0, argv[4]); else distingue(reference, argv[2], argv[3]); } else if ((!strcmp(argv[1],"-s"))&&(argc==3)) tous_les_sousmots(stdout, argv[2]); else if ((!strcmp(argv[1],"-s"))&&(argc==4)) { if ((reference=fopen(argv[3], "w"))==0) error(5, 0, argv[3]); else tous_les_sousmots(reference, argv[2]); } else if ((!strcmp(argv[1],"-x"))&&(argc==3)) { init_automate(&autom); dummy=lit_fichier(argv[2], &autom); ecrit_automate(stdout, &autom); } else { fprintf(stdout, "\n\n\n\nNOM"); fprintf(stdout, "\n sousmot - outil de recherche de sousmots "); fprintf(stdout, "\n\nDESCRIPTION"); fprintf(stdout, "\n Projet d'Algorithmique - Licence Informatique, UMLV (FRANCE)"); fprintf(stdout, "\n Copyright (C) 2000 Daniele Raffo "); fprintf(stdout, "\n\nSYNOPSIS"); fprintf(stdout, "\n sousmot [ -x fichier ] | [ -s mot [ reference ]] |"); fprintf(stdout, "\n [ -e fichier1 fichier2 ] | [ -m mot1 mot2 [ reference ]] |"); fprintf(stdout, "\n [ -h ]"); fprintf(stdout, "\n\nOPTIONS"); fprintf(stdout, "\n Les options suivantes sont supportees:"); fprintf(stdout, "\n\n -x Affiche sur stdout l'automate decrit sur fichier."); fprintf(stdout, "\n\n -s Affiche sur stdout la liste des sousmots du mot."); fprintf(stdout, "\n Si defini, la liste sera place' dans le fichier"); fprintf(stdout, "\n reference."); fprintf(stdout, "\n\n -e Teste l'equivalence des deux automates decrits"); fprintf(stdout, "\n dans fichier1 et fichier2. Le code de retour est"); fprintf(stdout, "\n 0 pour deux automates equivalents et 1 pour deux"); fprintf(stdout, "\n automates non equivalents."); fprintf(stdout, "\n\n -m Affiche sur stdout la liste des plus petits"); fprintf(stdout, "\n sousmots qui separent mot1 et mot2. Si defini, la"); fprintf(stdout, "\n liste sera place' dans le fichier reference."); fprintf(stdout, "\n\n -h Montre cette aide."); fprintf(stdout, "\n\n Sans parametres, le programme sera lance' en mode interactive.\n\n\n"); } } /* Initialisation du modele de donnees utilise' pour l'automate. */ void init_automate (automate *a) { int i, j, k; for (i=0;i<2*MAX_ETATS;i++) { a->status[i]=-1; for (j=0;jtable[i][j][k]=-1; } } /* Lit un fichier d'automate et le memorise dans le modele passe' en parametre, /* eventuellement apres un premier automate si celui-la' est deja' dans le modele. /* Retourne le nombre d'etats de l'automate lu. */ int lit_fichier(char *afile, automate *a) { void error(int erreur, int datanum, const char *datastr); FILE *fp; int n_etats, e, z, decalage; char y1, y2, y4, y5; int y3, y6; decalage=0; while (a->status[decalage]!=-1 && decalagestatus[e+decalage]=2; else if (y1=='-') a->status[e+decalage]=0; else { fclose(fp); error(4, e, afile); } fscanf(fp, "%c", &y2); /* lecture du fin de ligne ou d'une lettre */ if (y2=='\n') { e++; continue; } fscanf(fp, ",%d", &y3); /* lecture de la virgule et de l'etat d'arrivee */ /* les 4 lignes suivantes ajoutent l'etat d'arrivee dans la premiere place vide de la table */ z=0; while (a->table[e+decalage][(int)y2][z]!=-1) { z++; if (z==MAX_TRANS) { fclose(fp); error(2, 0, NULL); } } a->table[e+decalage][(int)y2][z]=y3+decalage; while (TRUE) { fscanf(fp, "%c", &y4); /* lecture du pointvirgule ou de la fin de ligne */ if (y4=='\n') { e++; break; } else if (y4==';') { /* do nothing */ } else { fclose(fp); error(4, e, afile); } fscanf(fp, "%c,%d", &y5, &y6); /* lecture d'une transition complete */ z=0; while (a->table[e+decalage][(int)y5][z]!=-1) { z++; if (z==MAX_TRANS) { fclose(fp); error(2, 0, NULL); } } a->table[e+decalage][(int)y5][z]=y6+decalage; } } fclose(fp); a->status[0+decalage]+=1; /* transforme en initial l'etat 0 */ return(n_etats); } /* Ecrit l'automate sur l'ecran ou sur fichier, selon le pointeur a' fichier passe' en parametre. */ void ecrit_automate(FILE *fp, const automate *a) { int n_etats; int i, j, k, e, h, hh; char *str_status; n_etats=0; while (a->status[n_etats]!=-1 && n_etatsstatus[i]) { case 0: str_status=" "; break; case 1: str_status=" (Initial) "; break; case 2: str_status=" (Terminal)"; break; case 3: str_status=" (InitTerm)"; break; } fprintf(stdout, "\nEtat %2d%s: ", i, str_status); for (j=0;jtable[i][j][0]!=-1) fprintf(stdout, "--%c--> ", (char)j); for (k=0;a->table[i][j][k]!=-1;k++) fprintf(stdout, "%d ", a->table[i][j][k]); if (a->table[i][j][0]!=-1) fprintf(stdout, " "); } } printf("\n"); } if (fp!=stdout) { /* ecriture de l'automate sur fichier */ fprintf(fp, "%d\n", n_etats); /* ecrit le nombre d'etats */ for (e=0;estatus[e]>=2) fprintf(fp, "+"); else fprintf(fp, "-"); for (h=0;htable[e][h][0]!=-1) { fprintf(fp, "%c,%d", (char)h, a->table[e][h][0]); break; } for (hh=h+1;hhtable[e][hh][0]!=-1) fprintf(fp, ";%c,%d", (char)hh, a->table[e][hh][0]); fprintf(fp, "\n"); } fclose(fp); } return; } /* Gere les situations d'erreur. /* Les parametres sont le type d'erreur et des informations additionnelles. */ void error(int erreur, int datanum, const char *datastr) { fprintf(stderr, "\nErreur: "); switch(erreur) { case 1: fprintf(stderr, "automate trop grand (max %d etats)", MAX_ETATS); break; case 2: fprintf(stderr, "trop de transitions pour une meme lettre depuis un meme etat "); fprintf(stderr, "(max %d transitions)", MAX_TRANS); break; case 3: fprintf(stderr, "impossible d'ouvrire le fichier %s pour lecture", datastr); break; case 4: fprintf(stderr, "fichier %s malforme' dans l'etat %d, ligne %d", datastr, datanum, datanum+2); break; case 5: fprintf(stderr, "impossible d'ecrire le fichier %s", datastr); break; case 6: fprintf(stderr, "mot %s trop long (max %d characteres)", datastr, MAX_L_MOT); break; case 7: fprintf(stderr, "l'automate %s n'est pas complet", datastr); break; case 8: fprintf(stderr, "les transitions des deux automates ne sont pas definis sur le meme langage"); break; } fprintf(stderr, "\n\n"); exit(-erreur); } /* Verifie si un automate est complet. */ int est_complet(const automate *a) { int n_etats, i, j; n_etats=0; while (a->status[n_etats]!=-1 && n_etatstable[i][j][0]==-1)&&(a->table[0][j][0]!=-1)) return(FALSE); if ((a->table[0][j][0]==-1)&&(a->table[i][j][0]!=-1)) return(FALSE); } return(TRUE); } /* Teste si le deux AFD complets lequel fichiers sont passes en parametre reconnaissent le meme langage. /* Retourne 0 s'ils sont equivalents, 1 s'ils ne le sont pas. */ int equiv_automate(char *afile1, char *afile2) { int lit_fichier(char *afile, automate *a); void init_automate(automate *a); void ecrit_automate(FILE *fp, const automate *a); void equiv(int e1, int e2, const automate *a, int classe[]); int est_complet(const automate *a); automate atest; int classe[2*MAX_ETATS]; int start2, tot_etats; int i, p, q; init_automate(&atest); /* lit les fichiers des deux automates et memorise ces derniers dans un meme modele, /* l'un apres l'autre, avec conseguente renumerotation des etats du deuxieme automate */ start2=lit_fichier(afile1, &atest); if (!est_complet(&atest)) error(7, 0, afile1); /* teste si le premier automate est complet */ init_automate(&adummy); dummy=lit_fichier(afile2, &adummy); if (!est_complet(&adummy)) error(7, 0, afile2); /* teste si le deuxieme automate est complet */ tot_etats=start2+lit_fichier(afile2, &atest); if (!est_complet(&atest)) error(8, 0, NULL); /* teste si le deux automates ont les etiquettes /* des transitions definies sur un meme langage, /* en testant si l'automate globale est complet */ /* le premier automate commence a' atest->table[0][][], le deuxieme a' atest->table[start2][][] */ if (TRACEON) ecrit_automate(stdout, &atest); for (i=0;istatus[tot_etats]!=-1 && tot_etatsstatus[t]); } if ((a->status[e1]>=2 && a->status[e2]<2) || (a->status[e2]>=2 && a->status[e1]<2)) equivhalt=TRUE; /* si un des etats e1 et e2 est terminal et l'autre pas, les deux automates ne sont pas equivalents */ x=classe[e1], y=classe[e2]; if (x!=y) { for (n=0;ntable[e1][l][0]!=-1) equiv(a->table[e1][l][0], a->table[e2][l][0], a, classe); } } /* Retourne un automate deterministe complet qui reconnait tous les sousmots du mot passe' en parametre. */ automate automate_sousmots(const char mot[]) { void init_automate(automate *a); int temp[MAX_L_MOT+2][MAX_L_MOT]; /* table temporaire des transitions pour le traitement du mot */ automate as; int longueur_mot, n_etats, poubelle, lettres_diff; int n, i, u, v, w, j, k, h; const int NONVALIDE=MAX_L_MOT+5; if (strlen(mot)>MAX_L_MOT) error(6, 0, mot); for (longueur_mot=0;mot[longueur_mot]!='\0';longueur_mot++) ; /* trouve le nombre de lettres du mot */ n_etats=longueur_mot+2; /* nombre d'etats de l'automate */ poubelle=n_etats-1; /* nombre de l'etat poubelle (c'est le dernier etat) */ /* remplissage de la table temporaire */ for (n=0;n=n) temp[n][i]=i+1; else temp[n][i]=poubelle; } if (TRACEON) { fprintf(stdout, "\n\n "); for (u=0;ustatus[n_etats]!=-1 && n_etatstable[0][n][0]; if ((transition!=-1)&&(transition!=poubelle)) { liste_ecriture[index_ecr].sousmot[0]=(char)n; liste_ecriture[index_ecr].sousmot[1]='\0'; liste_ecriture[index_ecr].terminus=transition; index_ecr++; } } } else { /* ecriture des sousmots obtenus a' partir de ceux de la liste_lecture */ for (;liste_lecture[index_lect].terminus!=-1;index_lect++) { for (n=0;ntable[(liste_lecture[index_lect].terminus)][n][0]; if ((transition!=-1)&&(transition!=poubelle)) { strcpy(liste_ecriture[index_ecr].sousmot, liste_lecture[index_lect].sousmot); suffix=strlen(liste_ecriture[index_ecr].sousmot); liste_ecriture[index_ecr].sousmot[suffix]=(char)n; liste_ecriture[index_ecr].sousmot[suffix+1]='\0'; /* ajoute la lettre de chaque transition au sousmot lu /* pour obtenir un sousmot de longueur majore' de 1 */ liste_ecriture[index_ecr].terminus=transition; index_ecr++; } } } } return; } /* Initialise la liste des sousmots. */ void init_liste(liste_sousmots *liste) { int i; for (i=0; iMAX_L_MOT) error(6, 0, mot_a_traiter); init_automate(&amot); init_liste(liste_lect); init_liste(liste_ecr); amot=automate_sousmots(mot_a_traiter); if (TRACEON) fprintf(stdout, "\n SOUSMOT TERMINUS"); for (l=1;l<=strlen(mot_a_traiter);l++) { /* trouve les sousmots de longueur l */ sousmots(&amot, liste_lect, liste_ecr); for (m=0;liste_ecr[m].terminus!=-1;m++) { if (TRACEON) fprintf(stdout, "\n%3d) %-16s %2d", ++count, liste_ecr[m].sousmot, liste_ecr[m].terminus); if ((!TRACEON)||((TRACEON)&&(fp!=stdout))) fprintf(fp, "%s\n", liste_ecr[m].sousmot); } /* la vieille liste d'ecriture des sousmots de longueur l devient la liste de lecture /* qui servira a' la creation des sousmots de longueur l+1 */ for (c=0;cMAX_L_MOT) error(6, 0, mot1); if (strlen(mot2)>MAX_L_MOT) error(6, 0, mot2); init_liste(liste_lect1); init_liste(liste_ecr1); init_liste(liste_lect2); init_liste(liste_ecr2); amot1=automate_sousmots(mot1); amot2=automate_sousmots(mot2); if (!strcmp(mot1, mot2)) return; /* si le mots sont egaux, on ne fait meme pas demarrer l'algorithme */ for (l=1;l<=(strlen(mot1)>strlen(mot2)?strlen(mot1):strlen(mot2));l++) { /* trouve les sousmots de longueur l des deux mots */ sousmots(&amot1, liste_lect1, liste_ecr1); sousmots(&amot2, liste_lect2, liste_ecr2); /* fait la separation entre le deux groupes de sous mots */ if (TRACEON) fprintf(stdout, "TEST GROUPE DE LONGUEUR %d ...\n", l); for (m1=0;liste_ecr1[m1].terminus!=-1;m1++) { unique=TRUE; for (m2=0;liste_ecr2[m2].terminus!=-1;m2++) { if (!strcmp(liste_ecr1[m1].sousmot, liste_ecr2[m2].sousmot)) { liste_ecr2[m2].unique=FALSE; unique=FALSE; break; } } if (unique) { separateurs=TRUE; fprintf(fp, "%s\n", liste_ecr1[m1].sousmot); } } for (m2=0;liste_ecr2[m2].terminus!=-1;m2++) { if (liste_ecr2[m2].unique) { separateurs=TRUE; fprintf(fp, "%s\n", liste_ecr2[m2].sousmot); } } /* si separateurs=TRUE, on a trouve' des sous-mots qui distinguent, /* sinon il faut faire un autre tour avec les sousmots de longueur l+1 */ if (separateurs) return; /* fait la copie de liste_ecriture sur la liste_lecture et initialise les flags d'unicite' des sousmots */ for (i=0;i