logo

expression reguliere


iutexpression reguliere

#msg2814656 Posté le 07-01-10 à 19:19
Posté par Profilcotentin53 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++
re : expression reguliere#msg2814680 Posté le 07-01-10 à 19:28
Posté par Profilmonrow monrow Posteur d'énigmes

Salut

A quoi correspond le |? le OU?
re : expression reguliere#msg2814758 Posté le 07-01-10 à 19:54
Posté par Profilcotentin53 cotentin53

salut,

cela veut dire : concatenation
re : expression reguliere#msg2814763 Posté le 07-01-10 à 19:56
Posté par Profilmonrow monrow Posteur d'énigmes

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 ...
re : expression reguliere#msg2814773 Posté le 07-01-10 à 20:04
Posté par Profilcotentin53 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 ....
re : expression reguliere#msg2814777 Posté le 07-01-10 à 20:05
Posté par Profilcotentin53 cotentin53

pardon le | est un ou effectivement

DSL
re : expression reguliere#msg2814780 Posté le 07-01-10 à 20:07
Posté par Profilmonrow monrow Posteur d'énigmes

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
re : expression reguliere#msg2814784 Posté le 07-01-10 à 20:09
Posté par Profilmonrow monrow Posteur d'énigmes

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

pour un ou, tu fais sortir deux flèche de ton état, chacun pourune partie
re : expression reguliere#msg2814793 Posté le 07-01-10 à 20:11
Posté par Profilcotentin53 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
re : expression reguliere#msg2814797 Posté le 07-01-10 à 20:14
Posté par Profilmonrow monrow Posteur d'énigmes

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) ...
re : expression reguliere#msg2814801 Posté le 07-01-10 à 20:15
Posté par Profilmonrow monrow Posteur d'énigmes

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?
re : expression reguliere#msg2814833 Posté le 07-01-10 à 20:30
Posté par Profilcotentin53 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
re : expression reguliere#msg2814879 Posté le 07-01-10 à 20:46
Posté par Profilcotentin53 cotentin53

cela devrait, enfin de mon avis, apeupres un truc dans le genre
suis je dans la bonne direction
a++
re : expression reguliere#msg2814881 Posté le 07-01-10 à 20:47
Posté par Profilcotentin53 cotentin53

avec le fichier cela serait mieux

re : expression reguliere#msg2814888 Posté le 07-01-10 à 20:48
Posté par Profilmonrow monrow Posteur d'énigmes

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 !
re : expression reguliere#msg2814916 Posté le 07-01-10 à 21:05
Posté par Profilmonrow monrow Posteur d'énigmes

Je te donne ce que je trouve ...

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

re : expression reguliere#msg2815544 Posté le 08-01-10 à 13:57
Posté par Profilcotentin53 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

Répondre à ce sujet

réservé Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster
attention Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.



maths haut de pagehaut Retrouvez cette page sur ilemaths l'île des mathématiques
© Tom_Pascal & Océane 2012