Projet Informatique Théorique 2016
Instructions et Documentation
Structures de données | Définitions de type | Fonctions
Référence du fichier automate.h
#include "ensemble.h"

Aller au code source de ce fichier.

Structures de données

struct  Automate
 Le type d'un automate. Plus de détails...
 
struct  Cle
 

Définitions de type

typedef struct Automate Automate
 
typedef struct Cle Cle
 

Fonctions

Automatecreer_automate ()
 Crée un automate vide, sans états, sans lettres et sans transitions. Plus de détails...
 
void liberer_automate (Automate *automate)
 Détruit un automate. Plus de détails...
 
void ajouter_etat (Automate *automate, int etat)
 Ajoute un état à un automate passé en paramètre. Plus de détails...
 
void ajouter_lettre (Automate *automate, char lettre)
 Ajoute une lettre à l'alphabet d'un automate passé en paramètre. Plus de détails...
 
void ajouter_transition (Automate *automate, int origine, char lettre, int fin)
 Ajoute une transition à l'automate passé en paramètre. Plus de détails...
 
void ajouter_etat_final (Automate *automate, int etat_final)
 Ajoute un état final à un automate passé en paramètre. Plus de détails...
 
void ajouter_etat_initial (Automate *automate, int etat_initial)
 Ajoute un état initial à un automate passé en paramètre. Plus de détails...
 
const Ensembleget_etats (const Automate *automate)
 Renvoie l'ensemble des états d'un automate. Plus de détails...
 
const Ensembleget_initiaux (const Automate *automate)
 Renvoie l'ensemble des états intiaux d'un automate. Plus de détails...
 
const Ensembleget_finaux (const Automate *automate)
 Renvoie l'ensemble des états finaux d'un automate. Plus de détails...
 
const Ensembleget_alphabet (const Automate *automate)
 Renvoie l'alphabet d'un automate. Plus de détails...
 
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. Plus de détails...
 
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. Plus de détails...
 
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. Plus de détails...
 
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. Plus de détails...
 
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. Plus de détails...
 
Ensembledelta1 (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 lettre donnée en paramètre. Plus de détails...
 
Ensembledelta (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 lisant une lettre donnée en paramètre. Plus de détails...
 
Ensembledelta_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 lisant un mot donné en paramètre. Plus de détails...
 
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. Plus de détails...
 
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 paramètre. Plus de détails...
 
Automatetranslater_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 ceux du second automate passé en paramètre. Plus de détails...
 
Automatetranslater_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 par un entier. Plus de détails...
 
int get_max_etat (const Automate *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. Plus de détails...
 
Automatecopier_automate (const Automate *automate)
 Copie un automate. Plus de détails...
 
Automatemot_to_automate (const char *mot)
 Renvoie un automate qui reconnaît un unique mot passé en paramètre. Plus de détails...
 
Ensembleetats_accessibles (const Automate *automate, int etat)
 
Ensembleaccessibles (const Automate *automate)
 
Automateautomate_accessible (const Automate *automate)
 
Automatecreer_automate_du_melange (const Automate *automate1, const Automate *automate2)
 
void print_automate (const Automate *automate)
 Affiche sur l'entrée standard (stdout) l'automate passé en paramètre. Plus de détails...
 
Automatecreer_union_des_automates (const Automate *automate_1, const Automate *automate_2)
 
Automatemiroir (const Automate *automate)
 

Documentation des fonctions

Automate* creer_automate ( )

Crée un automate vide, sans états, sans lettres et sans transitions.

Renvoie
L'automate créé.

Définition à la ligne 91 du fichier automate.c.

void liberer_automate ( Automate automate)

Détruit un automate.

Paramètres
automateL'automate à détruire.

Définition à la ligne 168 du fichier automate.c.

void ajouter_etat ( Automate automate,
int  etat 
)

Ajoute un état à un automate passé en paramètre.

Paramètres
automateUn automate.
etatL'état à ajouter.

Définition à la ligne 198 du fichier automate.c.

void ajouter_lettre ( Automate automate,
char  lettre 
)

Ajoute une lettre à l'alphabet d'un automate passé en paramètre.

Paramètres
automateUn automate.
lettreLa lettre à ajouter.

Définition à la ligne 202 du fichier automate.c.

void ajouter_transition ( Automate automate,
int  origine,
char  lettre,
int  fin 
)

Ajoute une transition à l'automate passé en paramètre.

Si les états et la lettre de la transition n'existent pas dans l'automate, alors la lettre et les états sont ajoutés automatiquement à l'automate.

Paramètres
automateUn automate.
origineL'origine de la transition.
lettreLa lettre de la transition.
finLa fin de la transition.

Définition à la ligne 206 du fichier automate.c.

void ajouter_etat_final ( Automate automate,
int  etat_final 
)

Ajoute un état final à un automate passé en paramètre.

Si l'état n'existe pas dans l'automate, l'état est ajouté automatiquement à l'automate.

Paramètres
automateUn automate.
etat_finalL'état final.

Définition à la ligne 226 du fichier automate.c.

void ajouter_etat_initial ( Automate automate,
int  etat_initial 
)

Ajoute un état initial à un automate passé en paramètre.

Si l'état n'existe pas dans l'automate, l'état est ajouté automatiquement à l'automate.

Paramètres
automateUn automate.
etat_initialL'état initial.

Définition à la ligne 233 du fichier automate.c.

const Ensemble* get_etats ( const Automate automate)

Renvoie l'ensemble des états d'un automate.

La mémoire de l'ensemble renvoyé est gérée par l'automate. L'utilisateur ne doit donc pas modifier ou libérer l'ensemble ainsi obtenu.

Paramètres
automateUn automate.
Renvoie
L'ensemble des états de l'automate.

Définition à la ligne 182 du fichier automate.c.

const Ensemble* get_initiaux ( const Automate automate)

Renvoie l'ensemble des états intiaux d'un automate.

La mémoire de l'ensemble renvoyé est gérée par l'automate. L'utilisateur ne doit donc pas modifier ou libérer l'ensemble ainsi obtenu.

Paramètres
automateUn automate.
Renvoie
L'ensmble des états initiaux de l'automate.

Définition à la ligne 186 du fichier automate.c.

const Ensemble* get_finaux ( const Automate automate)

Renvoie l'ensemble des états finaux d'un automate.

La mémoire de l'ensemble renvoyé est gérée par l'automate. L'utilisateur ne doit donc pas modifier ou libérer l'ensemble ainsi obtenu.

Paramètres
automateUn automate.
Renvoie
L'ensmble des états finaux de l'automate.

Définition à la ligne 190 du fichier automate.c.

const Ensemble* get_alphabet ( const Automate automate)

Renvoie l'alphabet d'un automate.

La mémoire de l'ensemble renvoyé est gérée par l'automate.

Paramètres
automateUn automate.
Renvoie
L'ensmble des lettres de l'automate.

Définition à la ligne 194 du fichier automate.c.

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.

Paramètres
automateUn automate.
origineL'origine de la transition.
lettreLa lettre de la transition.
finLa fin de la transition.
Renvoie
1 ou 0.

Définition à la ligne 392 du fichier automate.c.

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.

Paramètres
automateUn automate.
etatUn état.
Renvoie
1 ou 0.

Définition à la ligne 399 du fichier automate.c.

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.

Paramètres
automateUn automate.
etatUn état.
Renvoie
1 ou 0.

Définition à la ligne 403 du fichier automate.c.

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.

Paramètres
automateUn automate.
etatUn état.
Renvoie
1 ou 0.

Définition à la ligne 407 du fichier automate.c.

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.

Paramètres
automateUn automate.
lettreUne lettre.
Renvoie
1 ou 0.

Définition à la ligne 411 du fichier automate.c.

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 lettre donnée en paramètre.

La mémoire de l'ensemble renvoyé par la fonction est laissée à la charge de l'utilisateur. L'utilisateur devra donc prendre soin de libérer la mémoire à la fin de son utilisation.

Paramètres
automateUn automate.
origineUn état.
lettreUne lettre.
Renvoie
L'ensemble des états accessibles.

Définition à la ligne 251 du fichier automate.c.

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 lisant une lettre donnée en paramètre.

La mémoire de l'ensemble renvoyé par la fonction est laissée à la charge de l'utilisateur. L'utilisateur devra donc prendre soin de libérer la mémoire à la fin de son utilisation.

Paramètres
automateUn automate.
etats_courantsL'ensemble des état origines.
lettreUne lettre.
Renvoie
L'ensemble des états accessibles.

Définition à la ligne 259 du fichier automate.c.

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 lisant un mot donné en paramètre.

La mémoire de l'ensemble renvoyé par la fonction est laissé à la charge de l'utilisateur. L'utilisateur devra donc prendre soin de libérer la mémoire à la fin de son utilisation.

Paramètres
automateUn automate.
etats_courantsL'ensemble des état origines.
motLe mot à lire.
Renvoie
L'ensemble des états accessibles.

Définition à la ligne 279 du fichier automate.c.

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.

Paramètres
automateUn automate.
motLe mot à reconnaître.
Renvoie
1 ou 0

Définition à la ligne 442 du fichier automate.c.

void pour_toute_transition ( const Automate automate,
void(*)(int origine, char lettre, int fin, void *data)  action,
void *  data 
)

La fonction passe en revue toutes les transitions de l'automate et appelle la fonction passée en paramètre.

La fonction qui sera executée (et qui a été passée en paramètre), doit posséder l'en-tête suivante : void NOM_FONCTION( int origine, char lettre, int fin, void* data ); Les pramètres 'origine', 'lettre' et 'fin' correspondent à l'origine, la lettre et la fin de la transitions en cours de parcours. Le paramètre 'data' est un pointeur qui sera identique à celui passé par le paramètre 'data' de la fonction pour_toute_transition().

Paramètres
automateUn automate.
actionLa fonction à exécuter.
dataLa donnée supplémentaire à passer en paramètre à la fonction 'action' executée à chaque transition.

Définition à la ligne 294 du fichier automate.c.

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 ceux du second automate passé en paramètre.

Paramètres
automateL'automate à copier.
automate_a_eviterL'automate à éviter.

Définition à la ligne 375 du fichier automate.c.

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 par un entier.

Paramètres
automateL'automate à copier.
tranlsationL'entier de translation.

Définition à la ligne 106 du fichier automate.c.

int get_max_etat ( const Automate automate)
A faire:
Renvoie l'état ayant le numéro le plus grand de l'automate passé en paramètre.

Si l'automate est vide (sans état), alors il renvoie INT_MIN. (voir limits.h pour la valeur de INT_MIN).

Paramètres
automateUn automate.

Définition à la ligne 38 du fichier automate.c.

int get_min_etat ( const Automate automate)

Renvoie l'état ayant le numéro le plus petit de l'automate passé en paramètre.

Si l'automate est vide (sans état), alors il renvoie INT_MAX. (voir limits.h pour la valeure de INT_MAX).

automate Un automate.

Définition à la ligne 47 du fichier automate.c.

Automate* copier_automate ( const Automate automate)

Copie un automate.

L'automate copié et l'automate à copier sont indépendants du point de vue de la mémoire.

Paramètres
automateL'automate à copier.
Renvoie
La copie de l'automate.

Définition à la ligne 319 du fichier automate.c.

Automate* mot_to_automate ( const char *  mot)

Renvoie un automate qui reconnaît un unique mot passé en paramètre.

Paramètres
motle mot à reconnaître.
Renvoie
Un automate.

Définition à la ligne 462 du fichier automate.c.

Ensemble* etats_accessibles ( const Automate automate,
int  etat 
)
A faire:
Renvoie l'ensemble des états accessibles à partir d'un état en lisant un mot quelcquonque.
Paramètres
automateUn automate.
etatL'état de départ.
Renvoie
L'ensemble des états accessibles.

Définition à la ligne 480 du fichier automate.c.

Ensemble* accessibles ( const Automate automate)
A faire:
Renvoie l'ensemble des états accessibles à partir des états initiaux en lisant un mot quelconque.
Paramètres
automateUn automate.
Renvoie
L'ensemble des états accessibles.

Définition à la ligne 484 du fichier automate.c.

Automate* automate_accessible ( const Automate automate)
A faire:
Renvoie l'automate passé en paramètre dont les états non accessibles ont été supprimés.
Paramètres
automateUn automate.
Renvoie
L'automate accessible.

Définition à la ligne 488 du fichier automate.c.

Automate* creer_automate_du_melange ( const Automate automate1,
const Automate automate2 
)
A faire:
Crée l'automate du mélange.

Crée un nouvel automate qui reconnaît les mots w tels que w est le mélange de deux mots w1 et w2 appartenant respectivement aux langages reconnus par l'automate 1 et par l'autoamte 2 passés en paramètre.

On peut définir le mélange récursivement par : melange( a.w1, b.W2 ) := a.melange( w1, b.w2 ) + b.melange( a.w1, w2 ) melange( w, epsilon ) := w melange( epsilon, w ) := w où w1, w2 et w3 sont des mots, a et b des lettres, epsilon l'epsilon transition et . la concaténation.

Paramètres
automate1Le premier automate.
automate2Le deuième automate.
Renvoie
L'automate du mélange.

Définition à la ligne 496 du fichier automate.c.

void print_automate ( const Automate automate)

Affiche sur l'entrée standard (stdout) l'automate passé en paramètre.

Paramètres
automateL'automate à afficher.

Définition à la ligne 423 du fichier automate.c.

Automate* creer_union_des_automates ( const Automate automate_1,
const Automate automate_2 
)
A faire:
Crée l'union des automates.

Cet automate reconnaît tous les mots qui sont reconus par l'un des deux automates passés en paramètre.

Paramètres
automate_1Le premier automate.
automate_2Le deuxième automate.
Renvoie
L'automate à créer.

Définition à la ligne 474 du fichier automate.c.

Automate* miroir ( const Automate automate)
A faire:
Renvoie l'automate miroir d'un automate.

Il s'agit de l'automate qui reconnaît les mots renversés du langage associé à l'automate passé en paramètre.

Paramètres
automateUn automate.
Renvoie
L'automate miroir.

Définition à la ligne 492 du fichier automate.c.