Version imprimable
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 ?Citation:
Envoyé par Clad3
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)
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 .
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.
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 ;).
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.
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)?Citation:
Envoyé par Clad3
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.
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 :)