[Graphe][Parcours] Chaines de caractères

**GyZmoO** · 25/05/2006, 19h15

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** · 25/05/2006, 22h58

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

**GyZmoO** · 26/05/2006, 00h35

Algo déterministe? C'est a dire ?

. . .

**Jedai** · 26/05/2006, 04h05

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** · 26/05/2006, 09h21

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** · 26/05/2006, 09h28

Envoyé par GyZmoO

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** · 26/05/2006, 11h28

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** · 26/05/2006, 11h47

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é

**Hephaistos007** · 26/05/2006, 11h50

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

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

**GyZmoO** · 26/05/2006, 11h51

C'est vrai que ces parenthèses ne servent pas a grand chose

Mais le truc c'est que, des fois elles ne servent pas, des fois elles servent et voila

**BizuR** · 26/05/2006, 16h12

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 ?

**Graffito** · 27/05/2006, 11h08

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.

**GyZmoO** · 27/05/2006, 19h00

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

, merci a tous pour vos réponses claires et efficaces

Je vous tiendrai au courant .

**Matthieu Brucher** · 28/05/2006, 21h48

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.

**benratti** · 31/05/2006, 23h42

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.

**Matthieu Brucher** · 01/06/2006, 08h09

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.

**benratti** · 01/06/2006, 09h57

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é.

**benratti** · 01/06/2006, 10h04

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/

**GyZmoO** · 01/06/2006, 22h38

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

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

Je vais regarder tout ça en tout cas, merci

[Graphe][Parcours] Chaines de caractères

Algorithmes et structures de données

Discussions similaires

Partager

Partager