Discussion :

[GyZmoO]

Bonjour a tous !

Je suis confronté a un problème que je n'arrive pas vraiment a résoudre, je vous explique : j'ai un graphe, ce graphe possède des arcs nommés (avec des lettres 'a' 'b' etc). Ensuite j'ai une chaine de caractère qui représente un parcours dans ce graphe, par exemple la chaine peut être :

[a;a;(b|a)] : cette chaine représente un chemin " a puis a puis a OU b "
En gros le point virgule représente la séquence de 2 parcours, et le | un choix possible entre 2 trajets.

Ici on voit bien qu'on peut avoir 2 chemins : le 1er : a a b et le 2nd : a a a.

Le problème ce que je n'arrive pas a trouver un algo qui lit caractère par caractère et qui sait quoi faire en fonction du caractère rencontré.

De plus les chaines peuvent être beaucoup plus compliquées, du style

[a;(b|(c;d)|d);b|a]

Voila j'espère avoir été assez clair et merci pour l'attention que vous pourrez porter a ce message

[Matthieu Brucher]

Tu ne veux pas tenter le coup de l'algo déterministe ?

[GyZmoO]

Algo déterministe? C'est a dire ? . . .

[Jedai]

Ces expressions sont des expressions régulières, pour bien faire il faut les compiler sous forme d'automates à états finis avant de les exécuter machinalement.

--
Jedaï

[Graffito]

Bonjour,

Le problème est-il de dévelloper l'expression afin de lister tous les chemins possibles ou y a-t-il un autre objectif ?

[Matthieu Brucher]

Algo déterministe? C'est a dire ? . . .

Un automate déterministe pour être plus exact D'abord on crée l'automate non déterministe, puis on le déterminise.

[GyZmoO]

Le problème est-il de dévelloper l'expression afin de lister tous les chemins possibles ou y a-t-il un autre objectif ?

C'est juste lister tous les chemins possibles, il n'y pas d'autre objectif a part ma satisfaction personnelle

Un automate déterministe c'est un automate qui pour une "lettre" donnée ne peut effectuer qu'un seul trajet c'est bien ça? Enfin je veux dire pour une même lettre il n'y pas plusieurs trajets possibles ?

Si c'est ça je comprend mais quand je me retrouve avec ma chaine de caractère, (par exemple : [a;(b|c;(a|b));b] ) je fais quoi ? J'avoue être un peu dans le flou la


Merci pour vos réponses !

[KiLVaiDeN]

Question :

Dans ton exemple, à quoi servent ces parenthèses :

Code :

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

[a;(b|c;(a|b));b]

ton expression ne serait-elle pas simplifiée en :

Code :

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

[a;b|c;a|b;b]

?

Il faut que tu te penches à mon avis sur les arbres syntaxiques; un arbre te donnera donc toutes les possibilités, je ne suis pas assez fort pour donner d'exemple désolé

[Matthieu Brucher]

Un automate déterministe c'est un automate qui pour une "lettre" donnée ne peut effectuer qu'un seul trajet c'est bien ça? Enfin je veux dire pour une même lettre il n'y pas plusieurs trajets possibles ?

C'est un algo dans lequel il n'y a qu'un seul état actif à la fois.

[Hephaistos007]

Le problème ce que je n'arrive pas a trouver un algo qui lit caractère par caractère et qui sait quoi faire en fonction du caractère rencontré.

C'est la définition du déterminisme . Pour l'instant ton automate est non-déterministe puisque que ton algo ne peut pas toujours décider quels chemins enprunter (c-a-d le chemin ne peut pas être déterminé). Rendre ton automate déterministe permet de résoudre ce problème.

La transformation de ton automate non-déterministe --> déterministe se fait à l'aide d'un algorithme judicieux que l'on trouve dans tous les bons livres traitant du sujet.