convertir un afn en afd

bonjour,

le but de cette discussion est de savoir où je me suis gouré

en suivant la méthode du dragon book pour faire un AFN pour l’expression régulière 'c*' (zéro, un ou plusieurs 'c’), on obtient l’AFN suivant:

  |      c        |   épsilone
-----------------------------------
0 | ensemble vide |     {1;3}
1 |     {2}       | ensemble vide
2 | ensemble vide |     {1;3}
3 | ensemble vide | ensemble vide

l’etat initial est l’état 0 et l’état final est l’état 3

une epsilone-fermeture d’un ensemble E d’états de l’AFN, est l’ensemble des état que l’on peut atteindre en partant d’un état de E et en ne suivant que des transitions épsilone, avec E est inclus dans l’épsilone-fermeture de E. nous allons appeler "trans(ensemble E,étiquette e)" l’ensemble des états dans lesquelles on aboutit en partant, dans l’AFN, d’un état de E par une transition e. D est la table de transition de l’AFD recherché. D_trans[E,e] signifie l’état atteint en partant de E et en suivant e, dans l’AFD.

on commence avec l'épsilone-fermeture de {0}, qui est {0;1;3}, soit A={0;1;3}
trans(A,c)={2}
B = epsilone-fermeture({2}) = {1;2;3}
le dragon book dit que, avec ces deux assertions, on en déduit que D_trans[A,c]=B
trans(B,c) = {2}
épsilone-fermeture({2})={1;2;3}=B        D_trans[B,c] = B
cela nous donne la table de l'AFD recherché:

``````text
  |  c
--------
A |  B
B |  B

or, dans l’AFN, il y a une transition épsilone de l’état 0 à l’état 3. On aurai donc plutôt dû obtenir un table d’AFD semblable à ceci:

  | c
------
A | A

quelqu’un voit-il où je me suis gouré?

or, dans l’AFN, il y a une transition épsilone de l’état 0 à l’état 3.

C’est la raison pour laquelle 3 fait partie de la fermeture de {0}, à savoir {0, 1, 3}. Je ne comprends pas quel est le raisonnement qui t’amène à ton automate.

Par contre, ces deux automates sont équivalents — la méthode du dragon book donne simplement un automate légèrement plus gros, mais plus facile à construire parce que complètement automatique.

ces deux automates diffèrent en le sens que le premier consomme au moins un 'c' tandis que l’autre, qui n’a qu’un seul état, un état d’acceptation, peut se terminer sans avoir consommé un seul 'c’.

le premier est calculé selon la méthode du dragon book et le deuxième est celui que j’aurai souhaité obtenir.

en tournant les page du livre, j’ai vu qu’ils proposent une méthode pour trouver un afd directement à partir d’une expression régulière, sans passer par un afn. J’arrête donc là la discussion

Merci Eusèbe, tu as raison.

résolu