Discussion :

[VivienD]

Bonsoir,


Ça fait longtemps que je ne m’étais pas montré sur le forum mais vu mon emploi du temps je pense que mon absence est tout à fait compréhensible.

Je souhaite toujours m’exercer et m’améliorer dans la programmation et je compte m’attaquer aux automates finis déterministes. En effet il s’agit selon moi d’un thème intéressant et sans doute utile (et qui pourrait me faire aboutir sur des thèmes plus complexes comme les automates non-déterministes, les automates non-finis et consorts).
J’ai en premier lieu organisé mon étude en plusieurs points que voici :

1. coder un automate fini déterministe «fixe»:
   
   1. créer des nœuds (initiaux, intermédiaires et finaux),
   2. créer des chemins étiquetés (chemins d’un nœud à un autre et chemins … récursifs?),
   3. assembler le tout pour avoir un automate et
   4. complexifier la chose (flux de données en plus des étiquettes, travail de ces dernières dans chacun des nœuds);
2. coder un automate fini déterministe «dynamique»;
3. si nécessaire.

Toutefois je bute sur un obstacle de taille: je n’ai pas la moindre idée sur la manière de commencer pour créer ne serait-ce qu’un nœud ou un chemin étiqueté…


Merci d’avance pour votre aide.


PS: Pour cela j’ai lu l’article de Wikipédia sur la théorie des automates finis. Si d’autres lectures me sont selon vous nécessaires, n’hésitez à m’en faire part.

[Neckara]

Si tu considère ton automate comme un graphe, tu peux faire la liste des successeurs, ou le tableau d'adjacence, etc...

En prenant pour chaque sommet un pointeur vers une fonction.

EDIT : bien sûr, il faut dans tes matrices, ajouter une dimension pour le choix effectué (chemin a, b ou c pour un alphabet à 3 lettres)

[sylafrs]

tu veux faire quelque chose comme ça ?

GRAPHE
- tableau de sommets
- tableau d'arcs
- *initial

SOMMET
- nom
- estFinal (boolean)

ARC
- *somSrc
- *somDst
- etiquette

(en fait je ne vois pas trop ton problème)

[anacharsis]

salut !
comme la question m’intéresse, j'ai fait une recherche google avec automate et Aho. il y a beaucoup de références universitaires sur le sujet et parfois même des algorithmes originaux ...
merci d'avoir ouvert ce sujet.

A+

[VivienD]

J'ai réfléchi à la question entre les cours, les projets, les rapports à remettre et les examens. Je suis encore au stade de l'algorithme mais voici ce que j'ai conclu de mes contorsions intellectuelles.

Admettons que mon automate ait n sommets, numérotés de 0 à (n-1) et que mon alphabet contienne p lettres, que je numérote de 0 à (p-1).
Dans un premier lieu je vais créer un vecteur qui listera toutes les lettres de mon alphabet. L'élément 0 de ce vecteur correspondra à la lettre n°0, l'élément 1 correspondra à lettre n°1, et ainsi de suite jusqu'à l'élément (p-1) qui correspondra à la lettre n°(p-1); le vecteur comprendra un élément supplémentaire, l'élément p, qui sera égal à une valeur ou un caractère qui ne sera pas présent dans mon alphabet (par exemple -1). Je le nommerai arcAlphabet.
Ensuite je vais créer un vecteur de pointeurs qui listera tous mes sommets comme précédemment: l'élément 0 de ce vecteur correspondra au sommet 0, et ainsi de suite jusqu'à l'élément (n-1) qui correspondra au sommet (n-1); et en sus le vecteur aura un élément supplémentaire, l'élément n, qui pointera vers NULL. Je le nommerai arpRegSommets[].
Chaque élément de ce dernier pointera un vecteur de (p-1) valeurs entières. Chacune des valeurs entières au numéro du sommet accessible via le chemin étiqueté par la lettre correspondante au numéro de l'élément. Je les définirai via la matrice arnSommets[][].
Enfin je créerai une structure arpRegAutomate qui pointera vers tous ces registres. La structure pourrait être définie comme ci-dessous.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
typedef struc{
     char *Alphabet;
     int *RegSommets;
     int *Sommets;
} _tAutomate;

C'est un premier jet donc il est à même d'être modifié s'il s'avère que le code est améliorable.