ennytiss, post:9, topic:133159 a écrit:
[quote=« ennytiss, post:6, topic:133159 »]
Merci beaucoup pour vos réponses (j’ai dû recréer mon compte car mon mot de passe ne marchait plus…).
[quote=« nolliac, post:5, topic:133159 »]
Bonjour,
Si tu communiques le sujet, je veux bien essayer de t’aider. Sinon, je ne pense pas que je pourrai vraiment.
@Inversion j’ai pris le sujet de là (c’est l’exercice 6): http://www.lirmm.fr/~poupet/enseignement/automates05/partiel-05.pdf
Cependant je voulais avant faire un exemple en dessinant un automate sur un alphabet à deux lettres par exemple, qui puisse reconnaître (par exemple) l’ensemble des mots ayant un nombre de lettres multiple de 4 et se terminant par b. Mais le truc avec les flèches me perturbe, est-ce que quand on dessine l’automate on ne met pas les flèches habituelles qu’on met dans les automates « normaux »? Je ne comprends pas trop. Merci !
[/quote]
Merci de m’avoir communiqué le sujet.
Si j’ai bien compris, quand tu dessines un automate boustrophédon, tu mets toujours les flèches que tu mets pour un automate « normal ». Simplement, à chaque transition (donc à chaque « flèche normale » qui est surmontée d’un élément de l’alphabet), tu indiques une petite flèche qui va soit vers la gauche soit vers la droite. Si la petite flèche va vers la droite, cela signifie que tu ajoutes l’élément de l’alphabet à la fin du mot que tu es en train de lire, et si la petite flèche va vers la gauche, tu l’ajoutes au contraire au début.
Par exemple si tu as :
q0 ---------> q1 --------------> q2 ------------> q3
|| a,<— |||||| b,-----> |||||| b, <------
avec q0 l’état initial et q3 l’unique état final, alors le seul mot reconnu par ton automate sera bab (les barres verticales sont juste un outil artisanal pour bien aligner les éléments de l’alphabet et les petites flèches sous les flèches de transition).
(d’abord tu ajoutes a par la transition (a, <—) puis par la transition (b, ---->) tu ajoutes b à la fin de ton mot ce qui fait ab puis par la transition (b, <-----) tu ajoutes b au début de ton mot ce qui fait bab).
C’est comme ça que je comprends la phrase « La capacité supplémentaire d’un automate boustrophédon par rapport à un automate
fini classique, est de pouvoir se déplacer sur le mot vers la droite et la gauche (là où un
automate fini ne peut qu’avancer vers la droite). »
Désolé pour le schéma un peu moyen.
[/quote]
wow je suis vraiment désolé, je pensais avoir répondu et là en voulant faire un tour je remarque que pas du tout ! c’est vraiment la honte… j’en suis vraiment désolé
je voulais te remercier pour tes explications, je n’avais pas du tout compris la chose comme ça mais grâce à toi j’ai bien compris maintenant !!! (et le schéma était très clair, je t’en remercie)
j’avais vu tes explications le jour même, ça m’a permis de comprendre et d’avancer dans le problème par la même occasion, mais visiblement je ne t’ai même pas répondu… ça ne se fait pas
bref, un grand merci à toi pour ton aide et tes explications, c’est devenu franchement plus clair !
