Discussion :

[emmesse]

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:

Code :

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

1
2
3
4
5
6
  |      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]=K signifie que K est l'état atteint en partant de l'état E et en suivant la transition 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é:

Code :

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

1
2
3
4
  |  c
--------
A |  B
B |  B

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

Code :

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

1
2
3
  | c
------
A | A

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

[Flodelarab]

Bonjour

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
(...)
quelqu'un voit-il où je me suis gouré?

Ben oui. Aucun état ne renvoie vers 0.
Donc 0 ne peut être une cible.
Donc A ne peut pas être un ensemble image.

Seuls 1, 2 et 3 sont des états atteignables.
Et comme par hasard, B={1,2,3}.

0 -> 1 -> 2
0 -> 3

A noter:
Les transformations gratuites (sans consommation de "c") n'atteignent que 1 et 3.
Il faut payer son "c" pour atterrir sur 2.

N'est-ce pas ?

[emmesse]

merci pour la réponse.
'c étoile" est zéro, un, ou plusieurs 'c'.
l'afd doit pouvoir faire zéro consommation de c.
on peut peut-être ajouter une transition "autre" comme pour un diagramme de transition.
à ce moment l'afd sera

Code :

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

1
2
3
4
   |     c  autre
-----------------------
A  |     A     B
B  |     /     /

A est une epsilone-fermeture de {0}, afin de donner un état initial au diagramme. C'est vrai, il n'y a aucune transition vers 0, mais il y a une epsilone-transition de 2 vers 1 pour consommer c à nouveau et une de 0 vers 3 pour que c ne soit jamais consommé

une idée?

[Flodelarab]

A est une epsilone-fermeture de {0}, afin de donner un état initial au diagramme.

Et bien fais-le !
{0,1,3} -> (1;2;3}
On n'atterrit sur B. Pas A.

Tant que tu t'obstineras à mettre 0 dans les images, ton analyse sera fausse. (A ne peut pas être dans la colonne "c" de ton tableau)

C'est vrai, (...) mais il y a (...)

Et alors ? Quel est la fin du raisonnement sous entendu ?

[emmesse]

en fait, voici ce que je voudrais obtenir:


zéro, un, ou plusieurs c dans l'afd final
d'après le dragon book, une epsilone-fermeture d'un ensemble contient cet ensemble car un états a implicitement une epsilone-transition sur lui-même

en fait cette discussion est finie car en tournant les pages du dragon book, ils expliquent comment obtenir un afd directement depuis l'expression régulière, sans passer par un afn.

je reviendrais sur developpez.net si j'ai des problèmes

merci pour ton aide

[emmesse]

Voici ce que l'on m'a dit sur un autre forum:
"Dans l’automate obtenu par la méthode systématique, les deux états sont finaux : un état du déterminisé est final s’il contient au moins un état final de l’afn de départ."

ce qui veut dire que l'état A du premier AFD est aussi un état final ( A={0;1;3} et 3 est l'état d'acceptation de l'AFN. A est donc aussi un état d'acceptation de l'AFD ). On peut donc ne consommer aucun 'c' avec cet AFD.