expression reguliere

Posté par cotentin53 cotentin53

Bonjour,

qui peux m'aider à construire l'automate correspondant à l'expression réguliere suivante :

E = (a*|b)|(b*|a)

je dois egalement calculer L'automate déterministe et l'automate minimal

je vous remercie d'avance pour votre aide

a++

Posté par monrow monrow

Salut

A quoi correspond le |? le OU?

Posté par cotentin53 cotentin53

salut,

cela veut dire : concatenation

Posté par monrow monrow

D'accord !

Qu'est ce t'as comme idée pour la première partie de l'expression : a*b ?

Un état initial avec un a qui boucle puis un .... je te laisse terminer ...

Posté par cotentin53 cotentin53

le a*b donne


   e     a   e
0 -> 1 -> 2 -> \
\               >   5
  -> 3 -> 4 -> /
   e    b   e

avec e pour e transition

puis un retour de 5 vers 0 pour *

c'est çà ?
par contre après ....

Posté par cotentin53 cotentin53

pardon le | est un ou effectivement

DSL

Posté par monrow monrow

les epsilon transitions, tu n'en as pas besoin ici ...

sinon ton automate ne reconnait que (ab)*

et puis il faut marquer l'état final

Posté par monrow monrow

ah d'accord ! je m'en doutais bien !

pour un ou, tu fais sortir deux flèche de ton état, chacun pourune partie

Posté par cotentin53 cotentin53

donc :

pour (a*|b) cela donne :
     a     b
0   ->  1  ->   2
^     /
   \---/

avec 2 etat final

et un retour de 1 vers 0 pour le a

Posté par monrow monrow

j'avoue ne pas troup comprendre ton schéma ... si tu pouvais le fair sur paint ou bien faire un apeçu avant de poster

Sinon me dire : les états sont ..... , j'ai une transition de .... à .... avec a ( ou b) ...

Posté par monrow monrow

sinon tu peux commencer par simplifier ton expression (a*|b)|(b*|a) c'est a* ou b ou b* ou a ... y a des trucs répétés ....

PS: t'es sûr que t'as un | entre les deux parties?

Posté par cotentin53 cotentin53

dsl pour le tps de reponse, j'ai du remdearrer mon pc

sinon ben oui justement, j'en ai tel qu'au premier post

je vais essayer d'en modeliser un

Posté par cotentin53 cotentin53

cela devrait, enfin de mon avis, apeupres un truc dans le genre
suis je dans la bonne direction
a++

Posté par cotentin53 cotentin53

avec le fichier cela serait mieux

Posté par monrow monrow

je suis désolé mais t'as oublié les flèches

et puis entre 0 et 1 t'as deux transitions, et tu n'as mis qu'un seul a !

Posté par monrow monrow

Je te donne ce que je trouve ...

Le langage reconnait soit a* soit b* (a ou bien b étant déjà inclus)

Posté par cotentin53 cotentin53

merçi
autre petite question :

peux t-on simplifier E = (a*|b)|(b*|a)

dans ce style là

E = (a*|b*)

merci d'avance