Discussion :

[zapatta]

Bonjour,
J'aurais besoin d'aide concernant la manipulation de chaine de caractère dans un automate déterministe.
L'automate comprend des état et des transitions entre les états qui ont pour valeur une lettre.
Mon automate est représenté par une matrice avec les dimensions suivantes :
[nombre d'états] [26] (pour les 26 lettres de l'alphabet ).
La matrice est initialisée à -1 et les lettres sont les transitions entre états. Par exemple si matrice[1][3]=2 alors on sait que l'état 2 est accessible depuis l'état 1avec le caractère 'c'.
L'état initial de l'automate est l'état 0 et plusieurs états pevent être finaux. (j'espère que j'ai été assez clair, c'est compliqué à expliquer ^^).
J'ai fait une fonction qui vérifie si un mot est disponible dans l'automate mais je dois maintenant faire une fonction qui me renvoie tous les mots de longueur inférieur à n pouvant être constitués avec l'automate. Je pense qu'il faut la faire en récursif mais je ne vois vraiment pas comment.
Si quelqu'un à une idée elle est la bienvenue !

[Graffito]

Bonjour,

Pour faciliter l'implémentation, il faut définir un état 0 pour l'état initial et un état F pour l'état final.

On travaillera sur une liste de chaines de caractères avec comme info associée à chaque mot sa longueur(Length) et l'état atteint au dernier caractère.

On peut alors créer une procédure qui traite un élément X de la liste pour ajouter à la liste tous les mots possibles de longueur Length(X)+1 :
Si Length(X)=N, on ne fait pas d'ajout,
Si Length(X)=N-1, on ajoute si l'état aprés transition est l'état final,
Sinon, on ajoute si cet état est différent de l'état final.

Après avoir créé le premier élément avec état initial 0 et longueur 0, il suffit d'appeler cette procedure successivement pour chaque élément rencontré dans la liste, ceci tant que toute la liste n'a pas été traitée.

La fin de la liste (qui est classée en ordre croissant de longueur) donnera tous les mots de longueur N possibles.

[Trap D]

Je pense que tu dois pouvoir résoudre ce problème avec une file, ayant comme élément une structure contenant la suite des lettres déjà rencontrées et l'état courant.
Tu initialises ta file avec l'état initial et 0 lettres lues.
Ensuite, tant que la file n'est pas vide, tu dépiles un élément, tu crées un nouvel élément copie de l'élément courant, et en fonction de l'état où tu es, tu ajoutes une lettre accessible et l'état obtenu, si c'est un état final tu t'arrètes et tu mémorises le mot, sinon si tu n'as pas atteint la longueur maximale n, tu mets l'élément dans la file.

[Matthieu Brucher]

Je me rappelle d'un sujet d'examen d'info de Polytechnique où on devait implémenter une automate qui reconnaissait si la chaîne correspondait à l'expression en entrée. C'était un truc tout simple avec gestion des * et des ? pour éviter potentiellement un caractère.

[Jean-Marc.Bourguet]

J'ai fait une fonction qui vérifie si un mot est disponible dans l'automate mais je dois maintenant faire une fonction qui me renvoie tous les mots de longueur inférieur à n pouvant être constitués avec l'automate.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
allwords: proc (size: int, prefix: string, state: state) is
   for c in character loop
      new_state: state = transition(state, c)
      if valid(new_state) then
         if accepting(new_state) then
            print_line prefix+c
         end
         if size > 1 then
            allwords size-1, prefix+c, new_state
         end
      end
   end

[zapatta]

C'est bon g réussi merci à tous !

[Trap D]

Et quelle solution as-tu prise ?