247 lines
8.4 KiB
C
247 lines
8.4 KiB
C
|
/********************************************/
|
||
|
|
/* Determinisation et Minimisation des NFAs */
|
||
|
|
/********************************************/
|
||
|
|
|
||
|
|
#include "nfa_determi.h"
|
||
|
|
#include "nfa.h"
|
||
|
|
|
||
|
|
/************************/
|
||
|
|
/* Procédure principale */
|
||
|
|
/************************/
|
||
|
|
|
||
|
|
// Fonction auxiliaire pour convertir une file d'états en une représentation
|
||
|
|
// entière unique
|
||
|
|
static uint dequeue_to_uint(dequeue *states) {
|
||
|
|
uint result = 0;
|
||
|
|
for (uint i = 0; i < size_dequeue(states); ++i) {
|
||
|
|
result |= (1 << lefread_dequeue(states, i));
|
||
|
|
}
|
||
|
|
return result;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Fonction auxiliaire pour vérifier si un ensemble d'états est final
|
||
|
|
static bool is_final_state(dequeue *states, dequeue *finals) {
|
||
|
|
for (uint i = 0; i < size_dequeue(states); ++i) {
|
||
|
|
if (mem_dequeue(lefread_dequeue(states, i), finals)) {
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Procédure de déterminisation. Le Booléen names indique si les noms des
|
||
|
|
// nouveaux états (des ensembles d'états de l'ancien NFA) doivent être
|
||
|
|
// sauvegardés dans le DFA.
|
||
|
|
nfa *nfa_determinize(nfa *thenfa, bool recording) {
|
||
|
|
printf("Déterminisation de l'automate1\n");
|
||
|
|
fflush(stdout);
|
||
|
|
// Créer un nouvel automate pour représenter le DFA
|
||
|
|
nfa *dfa = (nfa *)malloc(sizeof(nfa));
|
||
|
|
// Créer un graphe avec la taille de l'alphabet de l'automate initial
|
||
|
|
dfa->trans = create_lgraph_noedges(0, thenfa->trans->size_alpha);
|
||
|
|
dfa->initials = create_dequeue();
|
||
|
|
dfa->finals = create_dequeue();
|
||
|
|
// Copier les noms des lettres de l'alphabet;
|
||
|
|
dfa->alpha_names = nfa_copy_alpha(thenfa);
|
||
|
|
// Initialiser les noms des états si nécessaire
|
||
|
|
if (recording) {
|
||
|
|
dfa->state_names = (char **)malloc(sizeof(char *));
|
||
|
|
} else {
|
||
|
|
dfa->state_names = NULL;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Initialiser l'état initial du DFA
|
||
|
|
// recopier les états initiaux de l'automate initial
|
||
|
|
dequeue *initial_set = create_dequeue();
|
||
|
|
copy_dequeue_right(initial_set, thenfa->initials, 0);
|
||
|
|
// on les transforme en binaires
|
||
|
|
uint initial_state = dequeue_to_uint(initial_set);
|
||
|
|
// On ajoute l'état initial du DFA en decimal à la file des états initiaux du
|
||
|
|
// DFA
|
||
|
|
lefins_dequeue(initial_state, dfa->initials);
|
||
|
|
|
||
|
|
// Utiliser une file pour gérer les ensembles d'états à explorer
|
||
|
|
dequeue *queue = create_dequeue();
|
||
|
|
// Ajouter l'état initial à la file
|
||
|
|
lefins_dequeue(initial_state, queue);
|
||
|
|
|
||
|
|
// tableau de booléens pour marquer les états visités de taille 2^size_graph
|
||
|
|
barray *visited = create_barray(1 << thenfa->trans->size_graph);
|
||
|
|
// Marquer l'état initial comme visité
|
||
|
|
settrue_barray(visited, initial_state);
|
||
|
|
|
||
|
|
// Carte pour stocker les ensembles d'états réels
|
||
|
|
dequeue **state_sets =
|
||
|
|
(dequeue **)malloc((1 << thenfa->trans->size_graph) * sizeof(dequeue *));
|
||
|
|
// on int
|
||
|
|
state_sets[initial_state] = initial_set;
|
||
|
|
|
||
|
|
// Traiter chaque ensemble d'états
|
||
|
|
while (!isempty_dequeue(queue)) {
|
||
|
|
uint current_state = lefpull_dequeue(queue);
|
||
|
|
// stocke cet ensemble d'états initiaux dans le tableau `state_sets` à
|
||
|
|
// l'indice `initial_state`
|
||
|
|
dequeue *current_set = state_sets[current_state];
|
||
|
|
|
||
|
|
// Vérifier si l'état actuel est un état final
|
||
|
|
if (is_final_state(current_set, thenfa->finals)) {
|
||
|
|
lefins_dequeue(current_state, dfa->finals);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Traiter chaque lettre de l'alphabet
|
||
|
|
for (uint letter = 0; letter < thenfa->trans->size_alpha; ++letter) {
|
||
|
|
dequeue *next_set = create_dequeue();
|
||
|
|
|
||
|
|
// Calculer l'ensemble des états atteignables par la lettre actuelle
|
||
|
|
for (uint i = 0; i < size_dequeue(current_set); ++i) {
|
||
|
|
uint state = lefread_dequeue(current_set, i);
|
||
|
|
dequeue *transitions = thenfa->trans->edges[state][letter];
|
||
|
|
for (uint j = 0; j < size_dequeue(transitions); ++j) {
|
||
|
|
uint next_state = lefread_dequeue(transitions, j);
|
||
|
|
|
||
|
|
if (!mem_dequeue(next_state, next_set)) {
|
||
|
|
lefins_dequeue(next_state, next_set);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Convertir le prochain ensemble en une représentation entière unique
|
||
|
|
uint next_state = dequeue_to_uint(next_set);
|
||
|
|
|
||
|
|
// Si le prochain état n'a pas été visité, l'ajouter à la file et le
|
||
|
|
// marquer comme visité
|
||
|
|
if (!getval_barray(visited, next_state)) {
|
||
|
|
settrue_barray(visited, next_state);
|
||
|
|
lefins_dequeue(next_state, queue);
|
||
|
|
state_sets[next_state] = next_set;
|
||
|
|
} else {
|
||
|
|
delete_dequeue(next_set);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ajouter la transition au DFA
|
||
|
|
if (dfa->trans->size_graph <= current_state) {
|
||
|
|
dfa->trans->size_graph = current_state + 1;
|
||
|
|
dfa->trans->edges = (dequeue ***)realloc(
|
||
|
|
dfa->trans->edges, dfa->trans->size_graph * sizeof(dequeue **));
|
||
|
|
for (uint k = 0; k < dfa->trans->size_graph; ++k) {
|
||
|
|
dfa->trans->edges[k] =
|
||
|
|
(dequeue **)malloc(dfa->trans->size_alpha * sizeof(dequeue *));
|
||
|
|
for (uint l = 0; l < dfa->trans->size_alpha; ++l) {
|
||
|
|
dfa->trans->edges[k][l] = create_dequeue();
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
lefins_dequeue(next_state, dfa->trans->edges[current_state][letter]);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Enregistrer le nom de l'état si nécessaire
|
||
|
|
if (recording) {
|
||
|
|
char *state_name = (char *)malloc(256 * sizeof(char));
|
||
|
|
sprintf(state_name, "{");
|
||
|
|
for (uint i = 0; i < size_dequeue(current_set); ++i) {
|
||
|
|
if (i > 0) {
|
||
|
|
strcat(state_name, ",");
|
||
|
|
}
|
||
|
|
char buffer[10];
|
||
|
|
sprintf(buffer, "%u", lefread_dequeue(current_set, i));
|
||
|
|
strcat(state_name, buffer);
|
||
|
|
}
|
||
|
|
strcat(state_name, "}");
|
||
|
|
dfa->state_names[current_state] = state_name;
|
||
|
|
}
|
||
|
|
|
||
|
|
delete_dequeue(current_set);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Nettoyage
|
||
|
|
delete_dequeue(queue);
|
||
|
|
delete_barray(visited);
|
||
|
|
free(state_sets);
|
||
|
|
|
||
|
|
printf("Fin de la déterminisation1\n");
|
||
|
|
fflush(stdout);
|
||
|
|
return dfa;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Complementation
|
||
|
|
nfa *nfa_complement(nfa *thenfa) {
|
||
|
|
printf("Complémentation de l'automate\n");
|
||
|
|
fflush(stdout);
|
||
|
|
// Déterminiser l'automate
|
||
|
|
nfa *det_nfa = nfa_determinize(thenfa, false);
|
||
|
|
|
||
|
|
// Compléter l'automate déterminisé
|
||
|
|
uint num_states = det_nfa->trans->size_graph;
|
||
|
|
uint num_letters = det_nfa->trans->size_alpha;
|
||
|
|
printf("Complémentation de l'automate1\n");
|
||
|
|
fflush(stdout);
|
||
|
|
|
||
|
|
// Créer un nouvel état de puits
|
||
|
|
uint sink_state = num_states;
|
||
|
|
lgraph *new_trans = create_lgraph_noedges(num_states + 1, num_letters);
|
||
|
|
printf("Complémentation de l'automate2\n");
|
||
|
|
fflush(stdout);
|
||
|
|
// Copier les transitions existantes
|
||
|
|
for (uint state = 0; state < num_states; state++) {
|
||
|
|
for (uint letter = 0; letter < num_letters; letter++) {
|
||
|
|
printf("Complémentation de l'automate3\n");
|
||
|
|
fflush(stdout);
|
||
|
|
dequeue *transitions = det_nfa->trans->edges[state][letter];
|
||
|
|
if (transitions != NULL) {
|
||
|
|
printf("Complémentation de l'automate4\n");
|
||
|
|
fflush(stdout);
|
||
|
|
new_trans->edges[state][letter] = transitions;
|
||
|
|
} else {
|
||
|
|
printf("Complémentation de l'automate5\n");
|
||
|
|
fflush(stdout);
|
||
|
|
new_trans->edges[state][letter] = create_dequeue();
|
||
|
|
printf("Complémentation de l'automate6\n");
|
||
|
|
fflush(stdout);
|
||
|
|
rigins_dequeue(sink_state, new_trans->edges[state][letter]);
|
||
|
|
printf("Complémentation de l'automate7\n");
|
||
|
|
fflush(stdout);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ajouter des transitions vers l'état de puits pour les transitions
|
||
|
|
// manquantes
|
||
|
|
for (uint letter = 0; letter < num_letters; letter++) {
|
||
|
|
new_trans->edges[sink_state][letter] = create_dequeue();
|
||
|
|
rigins_dequeue(sink_state, new_trans->edges[sink_state][letter]);
|
||
|
|
}
|
||
|
|
|
||
|
|
printf("Complémentation de l'automate8\n");
|
||
|
|
fflush(stdout);
|
||
|
|
// Créer le nouvel automate avec les transitions complétées
|
||
|
|
nfa *comp_nfa = (nfa *)malloc(sizeof(nfa));
|
||
|
|
comp_nfa->trans = new_trans;
|
||
|
|
comp_nfa->initials = det_nfa->initials;
|
||
|
|
comp_nfa->alpha_names = nfa_copy_alpha(det_nfa);
|
||
|
|
comp_nfa->state_names = nfa_copy_all_names(det_nfa);
|
||
|
|
|
||
|
|
// Inverser les états finaux et non finaux
|
||
|
|
barray *finals_barray = create_barray(num_states + 1);
|
||
|
|
for (uint state = 0; state < num_states; state++) {
|
||
|
|
if (!mem_dequeue(state, det_nfa->finals)) {
|
||
|
|
settrue_barray(finals_barray, state);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
settrue_barray(finals_barray, sink_state);
|
||
|
|
|
||
|
|
// Créer la liste des états finaux
|
||
|
|
comp_nfa->finals = create_dequeue();
|
||
|
|
for (uint state = 0; state <= num_states; state++) {
|
||
|
|
if (getval_barray(finals_barray, state)) {
|
||
|
|
rigins_dequeue(state, comp_nfa->finals);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
printf("Complémentation de l'automate9\n");
|
||
|
|
fflush(stdout);
|
||
|
|
// Libérer la mémoire
|
||
|
|
delete_barray(finals_barray);
|
||
|
|
nfa_delete(det_nfa);
|
||
|
|
|
||
|
|
return comp_nfa;
|
||
|
|
}
|