Discussion :

[slim]

Bonjour,

Je passe l'examen d'un module (Automates et langages) la semaine prochaine (dans 10 jours).

Je suis arrivé à la fin de mon cours, ou il y a les differents algorithmes, non ecrits dans le cours, mais le principe est expliqué. Alors, la partie concerne la construction d'un AFN à partir d'une expression régulière et inversement. En fait, c'est l'inverse qui m'interesse.

j'ai l'exercice suivant :
soit un automate de la forme T = {A, Q, I, F, µ}
où A est l'alphabet reconnu par l'automate, Q est l'ensemble des états, I l'ensemble des états initiaux et F l'ensemble des états finaux avec µ les actions de l'automate (configurations, etapes.. ?)

soit un automate T1 = {{a,b}, {1,2,3,4,5,6}, {1,3}, {3,6}, µ}
µ est la suite des actions de l'automate, on peut les voir sur l'image ci-dessous. je peut les ecrire si vous voulez.

automate construit avec JFLAP.
je dois donner l'expression rationnelle r1 qui dénote le langage reconnu par T1 en passant par la résolution d'un systeme d'equations rationnelles.
Puis, donner un petit algo pour le passage de l'AFN à l'expression rationnelle. Mais le probleme, avant de faire l'algo, il faut savoir passer de l'AFN à l'er, or, je sais pas faire. Si quelqu'un peut m'aider s'il vous plait.
MErci beaucoup, vous me rendriez un big service.

P.S. : si je dois vous preciser quelque chose, demandez le moi (une partie du cours par exemple)

[slim]

je propose ca comme systeme d'equations rationnelles, mais je sais pas si c'est juste...


L1 = aL2
L2 = aL2 + bL6 + 1
L3 = bL4 + 1
L4 = aL4 + bL5
L5 = aL5 + bL6 + 1
L6 = aL6 + 1

merci bcp

[Clad3]

Je n'ai pas tout lu, et je suis pas trés doué niveau vocabulaire ... mais tes équations sont bonne a vue de nez
Pour résoudre ca, il faut appliquer le lemme d'arden ( ou un om de ce genre lol ) sur l'equation 6 puis ca va remonter tout seul

[slim]

j'ai trouvé :

L1 = aL2
L2 = aL2 + bL6
L3 = bL4 + 1
L4 = aL4 + bL5
L5 = aL5 + bL6
L6 = aL6 + 1

mais il faut résoudre ca et trouver une expression rationnelle.
J'essaie :

L6 = a*
L5 = a* + b(a*) = a* + ba* = a*ba*
L4 = a* + b(a*ba*) = ?
... et apres je me perds


merci...

[Clad3]

HUm j'avais lu un peu trop vite, d'ou sorte tes " 1 " ? c'est des Epsiolne? si oui je vois aps de sortie sur ton dessin de l'automate ... !?!

[slim]

je mets +1 quand c'est un etat final.

C'est epsilon effectivement.
pendant l'ecriture de l'er, il s'annule.

le double cercle signifie que c'est un etat final.

[Jedai]

Attention, a* + ba* ça ne fait pas a*ba* ! (si le + est bien une réunion comme c'est la convention). Par contre on a bien : L5 = aL5 + ba* = a*ba*
L4 = aL4 + ba*ba* = a*ba*ba*
L3 = ba*ba*ba* + 1
L2 = aL2 + bL6 = aL2 + ba* = a*ba*
L1 = aa*ba*

Finalement, on a :
L = L1 + L3 = aa*ba* + ba*ba*ba* + 1

Ce qui correspond bien à ton automate.

Maintenant les algos pour transformer un automate en regex sont multiples. L'un des plus simple à expliquer est l'algorithme par suppression d'état, mais je ne suis pas sûr qu'il soit évident à coder...

--
Jedaï

[slim]

Attention, a* + ba* ça ne fait pas a*ba* ! (si le + est bien une réunion comme c'est la convention).

Oui, c'est effectivement la convention mais pourquoi alors :

Par contre on a bien : L5 = aL5 + ba* = a*ba*

le plus est un "ou" ? donc on devrait mettre le signe |
comme cela : a* | ba*

enfin, je suis pas sur...
merci bco

P.S. : juste une "correction" pour L, voir en bas.

L6 = a*
L5 = a* + ba* + 1 = a*ba*
L4 = a* + b(a*ba*) = a*ba*ba*
L3 = ba*ba*ba* + 1 = ba*ba*ba*
L2 = a* + ba* = a*ba*
L1 = aa*ba* = a*ba*

L = L1 + L3 = a*ba* | ba*ba*ba*
puisqu'il y a deux etats initiaux, on met le signe | qui signifie "ou", Non ?

Cordialement
encore merci

[Jedai]

Ton L est faux.... En effet tu oublies le mot vide (que tu avais noté 1, notation que j'avais reprise, le mot vide fait partie de L puisqu'un état (3) est à la fois initial et final) et "b" ne fait pas partie de L (alors qu'il fait partie de a*ba*, mais pas du aa*ba* de ma réponse).

De plus tu semble confondre "L5 = aL5 | ba*" et "L5 = a* | ba*" qui sont très différent puisque la solution du premier est d'après le lemme d'Arden "a*ba*" tandis que le deuxième a pour solution "a* | ba*"...
Le + est un "ou", le | aussi, c'est juste une question de convention et du fait que le + fait plus "équation" que le |.

(NB : j'ai l'impression que tu ne comprends pas le lemme d'Arden, tu devrais le revoir)
(aa*ba* est différent de a*ba* !!!)
--
Jedaï