Discussion :

[Clad3]

Bonjour, je posséde un automate d'état finit, modeliser sous forme d'un graph .
Je posséde des methode type BFS DFS, disjsktra pour ce graph .
Je veut tester si un mot appartient au langage decrit par cet automate.

Je supose que ca doit etre faisable au moyen de l'un des 3 algo cci-dessus non?
Je suis preneur de vos conseils

[kaisse]

Bonjour, je posséde un automate d'état finit, modeliser sous forme d'un graph .
Je posséde des methode type BFS DFS, disjsktra pour ce graph .
Je veut tester si un mot appartient au langage decrit par cet automate.

Je supose que ca doit etre faisable au moyen de l'un des 3 algo cci-dessus non?
Je suis preneur de vos conseils

Que sont BFS et DFS ?
Tu as les transitions de ton automate (i.e. des arcs étiquetées dans ton graphe)?
Si oui, où est le problème ?
Sinon, je suis curieux de savoir comment tu pourrais t'en sortir ?

Sinon, laisse tomber Dijkstra (qui te permettra au mieux de trouver le plus petit (au sens de la longueur) mot qui appartient au langage, ce qui présente peu d'interet)

[Clad3]

BFS = parcours en largeur
DFS = parcours en profondeur

heu oui, j'ai mes transitions ( ini , lettre de passage, fin )
En faite, je ne epnse aps rencontré de problém majeur , mais je me demandais surtout si une methode + rapide utilisant un de ces algo existait .

[kaisse]

Tu ne peux, a priori, pas faire mieux que de faire faire toutes les transitions lettre à lettre et voir si tu arrives sur un état final. C'est efficace (linéaire). Si tu connais des propriétés spéciales de ton langage, alors oui, tu pourrais faire plus efficace, mais sinon, je ne vois pas d'autres solutions.

[Clad3]

hum vi, ce que tu décrit resmble a l'algo de mon cours
Enfin j'en suis pas la ... je suis au tout dbéut, entrain de calculer les "epsilone-fermeture )
Pour ca j'utilise l'algo de disktra, et je récupére tout les neoud accessible avec un coup de zéro .

[kaisse]

Les epsilon-fermetures ? C'est à dire quels états sont atteignables uniquement avec des epsilons-transitions ?

Si tu as des epsilon-transitions dans ton automate, ca veut dire qu'il est non-déterministe. Auquel cas, je te recommande d'appliquer un algorithme de determinisation sur ton automate avant de tester si un mot appartient au langage reconnu par cet automate (sinon, effectivement, l'algorithme devient facilement exponentiel). Telecharge le cours de Jean-François Rey sur ma page (http://perso.ens-lyon.fr/camille.vacher/theory.html) pour une introduction formelle aux automates et une description de l'algorithme de determinisation des automates.

[Clad3]

hehe JF rey est mon prof d'info j'ai telecharger son cours deja
Mais lors des tp, je doit calculer le langage reconnu par l'automate au TP 2, et faire un algo de déterminisation au tp3
merci du conseil quand meme !

[kaisse]

hehe JF rey est mon prof d'info j'ai telecharger son cours deja
Mais lors des tp, je doit calculer le langage reconnu par l'automate au TP 2, et faire un algo de déterminisation au tp3
merci du conseil quand meme !

Donc tu dois être à Cergy-Pontoise ? En deuxième année de DEUG MIAS sans doute (j'ai fait ca l'année dernière en deuxième année)?
Mais je ne comprends pas ce que tu dois faire: reconnaître des mots avec un automate ou dire explicitement quel est le langage reconnu par cet automate ? Dans le second cas, il faut que tu regardes les systèmes d'équations associés à un automate (chapitre 6 des cours 2-3) et que tu appliques le lemme d'Arden.

[Clad3]

ui, cergy, 2eme année

Enfin merci, je nai aps de probleme particulier
Je devais d'abord lire un automate dont les donnée ( états, transitions ) étaient ecrite dans un fichier sur le HD ( pas de pb ... ) et ensuite modéliser l'automate en question a l'aide d'un hashset ( en java ) ... mais bon j'ai trouvé que le xml et un bon graph sa rendait mieux le pb qu'un fichier txt et un conteneur simple ... enfin passons , ensuite il fallait que je test si un mot était reconnu ou pas par le langage de mon automate ( c'est fait )
Et la j'en suis a la partie ou je doit determiniser l'automate en question
Rien de bien difficile en vue, juste se rapeller de l'algo et le transcrire ... ca devrait aller lol ^^

enfin bon , merci pr les conseils tout de meme