Génération de tous les mots d'un automate Fermé

Question

Bonjour,

J'explique ma situation. 

Mon projet permet l'extraction  des attributs à partir d'une séquence biologique  via les automates. Après la création des automates, je veux générer automatiquement tous les mots possibles de ces automates et les mettre dans un tableau. 

Il y a quelqu'un qui peux m'aider et merci d'avance.

mx354 · Answer

Sur siemens , On utilise une fonction call .. Existe t'il ça en C Je ne sais pas bien à toi

sambia39 · Answer

Bonsoir 
C'est un peu vague ou j'ai très mal compris ce que tu voulais dire. 
Que veux-tu dire par automate de génération de mots ? concrètement de plus, je pense que c'est à partir d'une séquence biologique que ton automate te fournit des mots donc, pour faire simple, c'est à toi de faire une table de correspondance à ses différentes séquences pour que ton automatique puisse te fournir un mot ou un ensemble de groupe de mots. sans avoir plus de détails en ne peut vraiment t'aider.
à bientôt

manou901 · Answer

Bonsoir,
D'abord, je vais créer un automate avec expression régulière par exemple (a|b)c(g*). Puis, je vais générer tous les mots possibles de cet automate par exemple acg, acgg, bcgggg .... (je peux fixer une longueur maximale de mot si j'ai un boucle dans l'automate) .En fin, je vais insérer ces mots dans un tableau. J'espère j'ai bien expliqué le problème maintenant  et merci.

sambia39 · Answer

Bonjour 
Comme je tes répondus sur un autre forum, regarde plus du côté des transductions c'est plus de ce côté-là que tu peux trouver ton bonheur
à bientôt

manou901 · Answer

Bonjour,
Je suis en train d'écrire un pseudo code avant de l'implémenter en C, voila ce que j'ai pensé de faire :
Si je fixe une longueur maximale de mot, je peux le faire par récursion : je pars du début de l'automate ; en faisant une boucle sur tous les branchements possibles, je rajoutes la transition aux mots que je veux créer, et j' appelles ma fonction récursive sur chaque état pointée par mes transitions. Si j'obtiens un mot de longueur plus grande qu'un entier que je définis, j'arrêtes la récursion et je ne renvoies pas le mot. Si j'arrives sur l'état final de l'automate, idem, mais je renvoies le mot.
J'ai pensé d'utiliser plutôt des listes chaînées. 
je pense j'ai bien expliqué ou pas ?
a bientôt

caroline103 · Answer

Salut, il faut que tu fasse une analyse récursive des composants (lettres) de tes mots.
Exemple: Soit la liste de lettres "a$" de longueur "n"
Soit "m" le nombre de lettre de tes mots
Soit: "#w.txt," Un textbox (retour à la ligne à chaque boucle)
Algo:
    for i=1 to n 
       for j=i+1 to n
          for k=j+1 to n
             for m=k+1 to n-1
                #w.txt,word$(a$,i);" ";word$(a$,j);" ";word$(a$,k);" ";word$(a$,m)
//mise en ligne des lettres (" "<--espace entre chaque) pour former le mot 
//Syntaxe (word$...) en fonction du langage
             next m
          next k
       next j
    next i

fiddy · Answer

Bonjour, Effectivement, le plus simple est de le faire par récursivité. L'idée est de faire une fonction qui prend en argument le mot généré en cours, la taille et l'indice (qui s'incrémente à chaque à sous-appel de la fonction). Dans la fonction récursive, tu fais une seule boucle for (de 0 jusqu'à la longueur du mot souhaité) et tu appelles la fonction avec les différents paramètres et avec l'indice incrémenté de 1. La condition d'arrêt est lorsque la taille est égal à l'indice. Je te laisse réfléchir pour coder ça. N'hésite pas à poster ton code entre deux balises "code c" pour qu'on te corrige. Exemple : <"code c">/*ici tu mets ton code*/<"/code"> (sans les guillemets). Cdlt,

Génération de tous les mots d'un automate

7 réponses

Discussions similaires