[Graphe][Parcours] Chaines de caractères

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 :D

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

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

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ï

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 ?

Citation:

---

Envoyé par GyZmoO

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

---

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

Citation:

---

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 :D

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 :aie:


Merci pour vos réponses !

Question :

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

Code:

---

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

---

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

Code:

---

[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é :(

Citation:

---

Envoyé par GyZmoO

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 :D . 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.

C'est vrai que ces parenthèses ne servent pas a grand chose :D Mais le truc c'est que, des fois elles ne servent pas, des fois elles servent et voila :(

Petite question sur ton problème... peux tu enumérer l'ensemble des caractères trouvables sur ta chaine ? n'y a t il que ; et | ou retrouve-t-on des caractères de répétition (*),(+),(?) qui viendrait compliquer le tout si tu veux enumerer l'ensemble des possibilité. En gros, ta chaine peut elle proposer des sequences bouclées comme par exemple [a;(b;a)*;b] qui donnerait toutes les sequences a(ba)*b et dont le nombre de mot du langage deviendrai infini.

Si ce sont les seuls caractères, je pense qu'il serait adapté de transformer ton expression en arbre que tu parcourerais pour obtenir toutes les combinaisons...

L'automate serait plus utile je pense dans le cas de validation de mot du langage non ? :roll:

Bonjour,

Pour résoudre le problème une solution consiste à développer 3 fonctions :

1) Une addition de liste de chemins qui correspond à l'opérateur "|",
2) Une multiplication de liste de chemins qui correspond à l'opérateur ";",

Exemple : si Liste1={Cx,Cy} et Liste2={Cw,Cz}, alors
ADD(Liste1,Liste2)={Cx,Cy,Cw,Cz}
MULT(List1,LIST2)={Cx!!Cw,Cx!!Cz,Cy!!Cw,Cy!!Cz}
dans lequel "!!" représente la concaténation de 2 chemins

3) une procédure récursive ChercheChemins(Expression: argument d'entrée, Liste de chemins : argument de retour) :

procedure ChercheChemins(Expression,Liste)
begin
- tant qu'il y a des parenthéses encadrant l'expression, on les supprime.
- si l'expression est réduite à une lettre (exemple : "a"),
la liste contiendra 1 seul chemin de longueur 1 - on sort de la fonction -.
- on cherche le premier séparateur au niveau de parenthésage zéro
le niveau 0 au départ s'incrémente de 1 lorsqu'on rencontre une "("
et se décrémente si ")".
- on découpe alors l'expression en 2 Expressions exp1 et exp2.
- on exécute : ChercheChemins(Exp1,Liste1) et ChercheChemins(Exp2,Liste2).
- suivant l'opérateur entre exp1 et exp2,
on exécute Liste=ADD(Liste1,Liste2) ou Liste=MULT(Liste1,Liste2).
end ;

PS : La solution proposée considère que les 2 séparateurs sont d'égale priorité,
Si ce n'est pas le cas, il faudra rechercher le séparateur prioritaire d'abord.
Si pas de sep prioritaire trouvé, on recherchera alors le séparateur secondaire.

Citation:

---

Petite question sur ton problème... peux tu enumérer l'ensemble des caractères trouvables sur ta chaine ? n'y a t il que ; et | ou retrouve-t-on des caractères de répétition (*),(+),(?) qui viendrait compliquer le tout si tu veux enumerer l'ensemble des possibilité. En gros, ta chaine peut elle proposer des sequences bouclées comme par exemple [a;(b;a)*;b] qui donnerait toutes les sequences a(ba)*b et dont le nombre de mot du langage deviendrai infini.

---

Je peux avoir une fermeture * mais pour un parcours entier, c'est a dire je peux pas avoir [a;(b|a)*;g;d] je peux juste avoir [(a;b;b;b)*] .

Graffito, ta solution a l'air cool je vais tenter ça :D , merci a tous pour vos réponses claires et efficaces :mouarf:

Je vous tiendrai au courant .

Citation:

---

Envoyé par GyZmoO

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.

Juste pour information, tes chaines de caractères sont ce que l'on appelle des expression regulière. Elles permettre de definir ce que l'on appele un langage rationnel.

Ce que tu appeles graphe est aussi appele automate de mot.

Si tu es interessé par le sujet, il y a chose qui ont été faite sur le sujet. Tu peux commencer par un cours d'info théorique de licence par exemple celui ci qui n'est, je le reconnais, pas forcement tres accessible mais il existe d'autre ploy tres bien fait.

Les chapitres 3 et 6 pourront t'interessé particulièrement. Tu trouveras notamment le théorème de Kleene qui montre la correspondance entre Langage reconnaissable ( par un automate deterministe ) et langage rationnel. Bref, c'est plus ou moins ce que tu cherchais.

Ensuite, il est tres simple de simple d'implémenter un automate deterministe comme ceux que tu utilises.

Les cours de l'X sont quand même plutôt de niveau Bac+4 ou Bac+5 ;)
Mais faire un truc comme ça, c'est du niveau Bac+3 sans aucun pb, il suffit de connaître les automates déterministes - cours d'info de spé par exemple -. Pour en revenir à l'X, il y a un sujet d'info du concours d'entrée du début du millénaire qui consiste à créer un tel automate.

Juste pour info, j'ai suivi le meme cours que celui que j'ai cité en licence ( avec le meme prof ) à la fac...

Par contre, j'avais suivi des cours sur les automates et les langages rationnels en deuxième année de DEUG. Si je retrouve les cours, je peux vous passer les liens, c'est peut etre un peu plus accessible que les cours que j'ai filé.

Bon, j'ai trouve un cours plus accessible ( niveau bac +2 ) que j'avais suivi à une epoque :
va faire un tour sur cette page : http://www.lri.fr/ENSEIGNANTS/DEUG/S3-pil/

Merci énormément pour tous ces conseils\cours en tout genre :D

En fait je connais un peu tout ça, exp régulière automate fini déterministe et tout ça (je suis en L3 ^^) mais bon avec toutes les grêves\blocus des facs qu iL y a eu cette année on a survolé vite fait tout ça et donc je pompe pas grand chose :aie:

Je vais regarder tout ça en tout cas, merci :mouarf: